Real-time embedded software testing method based on extended finite state machine

The reliability of real-time embedded software directly determines the reliability of the whole real-time embedded sys- tem, and the effective software testing is an important way to ensure software quality and reliability. Based on the analysis of the characteristics of real-time embedded software, the formal method is introduced into the real-time embedded software testing field and the real-time extended finite state machine （RT-EFSM） model is studied firstly. Then, the time zone division method of real-time embedded system is presented and the definition and description methods of time-constrained transition equivalence class （timeCTEC） are presented. Furthermore, the approaches of the testing sequence and test case generation are put forward. Finally, the proposed method is applied to a typical avionics real- time embedded software testing practice and the examples of the timeCTEC, testing sequences and test cases are given. With the analysis of the testing result, the application verification shows that the proposed method can effectively describe the real-time embedded software state transition characteristics and real-time requirements and play the advantages of the formal methods in accuracy, effectiveness and the automation supporting. Combined with the testing platform, the real-time, closed loop and automated simulation testing for real-time embedded software can be realized effectively.

Global Control Simulation of Electric Vehicle Based on Finite State Machine Theory

Finite state machine theory (FSM) is introduced and applied to global control of electric vehicle. Theoretical adaptation for application of FSM in control of electric vehicle is analyzed. Global control logic for parts of electric vehicle is analyzed and built based on FSM. Using Matlab/Simulink, BJD6100-HEV global control algorithm is modeled and prove validity by simulation.

Application of Finite State Machine Theory to the Simulation of Reversed Non-Linear Hysteretic Relationships

This paper presents the application of finite state machine (FSM) theory to the programming of nonlinear hysteretic model simulation for both known and newly created rules. The complicated reversed internal paths involved in the nonlinear relationship which not only depend on material properties, but also on load history, often confuse rule creators and scholars. In this paper, we first describe the development of past hysteretic models. Then we introduce the FSM theory conceptually, and explain how it is applied to reversed and diverse routes. Next, state definitions and procedures are explained with a specific data example using the bilinear model. Finally, the successful application to UC-win/FRAME (3D) is described and several characteristics are summarized. By using FSM’s states and the linkages to represent a hysteresis model, we can quickly realize the programming of the defined complex model rules, and the nonlinear modeling becomes more efficient and feasible.

A matrix-based static approach to analysis of finite state machines

Traditional matrix-based approaches in the field of finite state machines construct state transition matrices,and then use the powers of the state transition matrices to represent corresponding dynamic transition processes,which are cornerstones of system analysis.In this study,we propose a static matrix-based approach that revisits a finite state machine from its structure rather than its dynamic transition process,thus avoiding the“explosion of complexity”problem inherent in the existing approaches.Based on the static approach,we reexamine the issues of closed-loop detection and controllability for deterministic finite state machines.In addition,we propose controllable equivalent form and minimal controllable equivalent form concepts and give corresponding algorithms.

State space optimization of finite state machines from the viewpoint of control theory

Motivated by the inconvenience or even inability to explain the mathematics of the state space optimization of finite state machines(FSMs)in most existing results,we consider the problem by viewing FSMs as logical dynamic systems.Borrowing ideas from the concept of equilibrium points of dynamic systems in control theory,the concepts of t-equivalent states and t-source equivalent states are introduced.Based on the state transition dynamic equations of FSMs proposed in recent years,several mathematical formulations of t-equivalent states and t-source equivalent states are proposed.These can be analogized to the necessary and sufficient conditions of equilibrium points of dynamic systems in control theory and thus give a mathematical explanation of the optimization problem.Using these mathematical formulations,two methods are designed to find all the t-equivalent states and t-source equivalent states of FSMs.Further,two ways of reducing the state space of FSMs are found.These can be implemented without computers but with only pen and paper in a mathematical manner.In addition,an open question is raised which can further improve these methods into unattended ones.Finally,the correctness and effectiveness of the proposed methods are verified by a practical language model.

Aspect-Oriented Modeling and Verification with Finite State Machines

Aspect-oriented programming modularizes crosscutting concerns into aspects with the advice invoked at the specified points of program execution. Aspects can be used in a harmful way that invalidates desired properties and even destroys the conceptual integrity of programs. To assure the quality of an aspect-oriented system, rigorous analysis and design of aspects are highly desirable. In this paper, we present an approach to aspect-oriented modeling and verification with finite state machines. Our approach provides explicit notations （e.g., pointcut, advice and aspect） for capturing crosscutting concerns and incremental modification requirements with respect to class state models. For verification purposes, we compose the aspect models and class models in an aspect-oriented model through a weaving mechanism. Then we transform the woven models and the class models not affected by the aspects into FSP （Finite State Processes）, which are to be checked by the LTSA （Labeled Transition System Analyzer） model checker against the desired system properties. We have applied our approach to the modeling and verification of three aspect-oriented systems. To further evaluate the effectiveness of verification, we created a large number of flawed aspect models and verified them against the system requirements. The results show that the verification has revealed all flawed models. This indicates that our approach is effective in quality assurance of aspect-oriented state models. As such, our approach can be used for model-checking state-based specification of aspect-oriented design and can uncover some system design problems before the system is implemented.

Intelligent decision-making method for vehicles in emergency conditions based on artificial potential fields and finite state machines

This study aims to propose a decision-making method based on artificial potential fields(APFs)and finite state machines(FSMs)in emergency conditions.This study presents a decision-making method based on APFs and FSMs for emergency conditions.By modeling the longitudinal and lateral potential energy fields of the vehicle,the driving state is identified,and the trigger conditions are provided for path planning during lane changing.In addition,this study also designed the state transition rules based on the longitudinal and lateral virtual forces.It established the vehicle decision-making model based on the finite state machine to ensure driving safety in emergency situations.To illustrate the performance of the decision-making model by considering APFs and finite state machines.The version of the model in the co-simulation platform of MATLAB and CarSim shows that the developed decision model in this study accurately generates driving behaviors of the vehicle at different time intervals.The contributions of this study are two-fold.A hierarchical vehicle state machine decision model is proposed to enhance driving safety in emergency scenarios.Mathematical models for determining the transition thresholds of lateral and longitudinal vehicle states are established based on the vehicle potential field model,leading to the formulation of transition rules between different states of autonomous vehicles(AVs).

基于EFSM的智能车间制造系统生产物流建模与仿真

制造业的生产物流方式处于不断变革中,对其建模仿真可为制造系统规划设计、分析及改造提供决策支持。依“人-机-物-环-法”分类给出了智能车间制造系统中实体元素的描述,结合EFSM(extended finite state machine)和组件化建模思想,建立了生产和物流组件化EFSM模型;阐述了智能车间多作业生产的建模过程以及组件模型实例化方法;通过EFSM-DEVS(discrete event system specification)模型自动转换及DEVS引擎完成了仿真运行。仿真结果表明:该方法所建立的模型更符合车间实际状况,适用性更广;组件化建模思想能构造更具扩展性的软件;建模及仿真运行的3D可视化使软件直观性更好,其仿真结果与AnyLogic保持一致。

Modeling and TOPSIS-GRA Algorithm for Autonomous Driving Decision-Making Under 5G-V2X Infrastructure

This paper is to explore the problems of intelligent connected vehicles(ICVs)autonomous driving decision-making under a 5G-V2X structured road environment.Through literature review and interviews with autonomous driving practitioners,this paper firstly puts forward a logical framework for designing a cerebrum-like autonomous driving system.Secondly,situated on this framework,it builds a hierarchical finite state machine(HFSM)model as well as a TOPSIS-GRA algorithm for making ICV autonomous driving decisions by employing a data fusion approach between the entropy weight method(EWM)and analytic hierarchy process method(AHP)and by employing a model fusion approach between the technique for order preference by similarity to an ideal solution(TOPSIS)and grey relational analysis(GRA).The HFSM model is composed of two layers:the global FSM model and the local FSM model.The decision of the former acts as partial input information of the latter and the result of the latter is sent forward to the local pathplanning module,meanwhile pulsating feedback to the former as real-time refresh data.To identify different traffic scenarios in a cerebrum-like way,the global FSM model is designed as 7 driving behavior states and 17 driving characteristic events,and the local FSM model is designed as 16 states and 8 characteristic events.In respect to designing a cerebrum-like algorithm for state transition,this paper firstly fuses AHP weight and EWM weight at their output layer to generate a synthetic weight coefficient for each characteristic event;then,it further fuses TOPSIS method and GRA method at the model building layer to obtain the implementable order of state transition.To verify the feasibility,reliability,and safety of theHFSMmodel aswell as its TOPSISGRA state transition algorithm,this paper elaborates on a series of simulative experiments conducted on the PreScan8.50 platform.The results display that the accuracy of obstacle detection gets 98%,lane line prediction is beyond 70 m,the speed of collision avoidance is higher than 45 km/h,the distance of collision avoidance is less than 5 m,path planning time for obstacle avoidance is averagely less than 50 ms,and brake deceleration is controlled under 6 m/s2.These technical indexes support that the driving states set and characteristic events set for the HFSM model as well as its TOPSIS-GRA algorithm may bring about cerebrum-like decision-making effectiveness for ICV autonomous driving under 5G-V2X intelligent road infrastructure.

Specifying Requirements of Real-Time System with Rules and Templates

This paper presents a model specifying requirements of real-time systems. Different from existing researches, this model mainly uses rules and templates to represent hierarchical FSMs (Finite State Machine). In this model, one rule corresponds to one state transition of FSM and one template corresponds to one FSM. Rules and information with respect to a FSM can be written in a template. So templates include not only state diagrams, but also information that can not be described by FSM, such as performance requirements. The specification using this model consists of a collection of templates and it is easy for users to understand and to review. After introduced the related researches and principles of the model, this paper specifies requirements of a real-time system with this model, and discusses characters of this model in the end.

Multiple UIO-based test sequence generation for distributed systems

In developing distributed systems, conformance testing is required to determine whether an implementation under test （IUT） conforms to its specification. With distributed test architectures involving multiple remote testers, testing approaches may become more complicated because of issues known as controllability and observability problems. Based on a finite state machine （FSM） representation of the system＇s specification, this paper proposes a new method to generate a test sequence utilizing multiple UIO sequences. The method is essentially guided by the way of minimizing the use of external coordination messages and input/output operations. Experiments are given to evaluate the proposed method.

OPEN ARCHITECTURE CNC SYSTEM HITCNC AND KEY TECHNOLOGY

Aiming at the characteristics of modularity and reconfigurable in open architecture computer numerical control （CNC） system, the open architecture CNC system, Harbin Institute of Tech- nology computer numerical control （HITCNC）, is researched and manufactured based on the interface standards. The system＇s external interfaces are coincident with the corresponding international standards, and the internal interfaces follow the open modular architecture controller （OMAC） agreement. In the research and manufacturing process, object-oriented technology is used to ensure the openness of the HITCNC, and static programming is applied in the CNC system according to the idea of modularization disassembly. The HITCNC also actualizes real-time and unreal-time modules adopting real-time dynamical linked library （RTDLL） and component object model （COM）. Finite state ma- chine （FSM） is adopted to do dynamically modeling of HITCNC. The complete separation between the software and the hardware is achieved in the HITCNC by applying the SoftSERCANS technique. The application of the above key techniques decreases the programming workload greatly, and uses software programs replacing hardware functions, which offers plenty technique ensures for the openness of HITCNC. Finally, based on the HITCNC, a three-dimensional milling system is established. On the system, series experiments are done to validate the expandability and interchangeability of HITCNC. The results of the experiments show that the established open architecture CNC system HITCNC is correct and feasible, and has good openness.

Formal Reduction of Interfaces to Large-scale Process Control Systems

A formal methodology is proposed to reduce the amount of information displayed to remote human operators at interfaces to large-scale process control plants of a certain type. The reduction proceeds in two stages. In the first stage, minimal reduced subsets of components, which give full information about the state of the whole system, are generated by determining functional dependencies between components. This is achieved by using a temporal logic proof obligation to check whether the state of all components can be inferred from the state of components in a subset in specified situations that the human operator needs to detect, with respect to a finite state machine model of the system and other human operator behavior. Generation of reduced subsets is automated with the help of a temporal logic model checker. The second stage determines the interconnections between components to be displayed in the reduced system so that the natural overall graphical structure of the system is maintained. A formal definition of an aesthetic for the required subgraph of a graph representation of the full system, containing the reduced subset of components, is given for this purpose. The methodology is demonstrated by a case study.

An EFSM-Based Test Data Generation Approach in Model-Based Testing

Testing is an integral part of software development.Current fastpaced system developments have rendered traditional testing techniques obsolete.Therefore,automated testing techniques are needed to adapt to such system developments speed.Model-based testing(MBT)is a technique that uses system models to generate and execute test cases automatically.It was identified that the test data generation(TDG)in many existing model-based test case generation(MB-TCG)approaches were still manual.An automatic and effective TDG can further reduce testing cost while detecting more faults.This study proposes an automated TDG approach in MB-TCG using the extended finite state machine model(EFSM).The proposed approach integrates MBT with combinatorial testing.The information available in an EFSM model and the boundary value analysis strategy are used to automate the domain input classifications which were done manually by the existing approach.The results showed that the proposed approach was able to detect 6.62 percent more faults than the conventionalMB-TCG but at the same time generated 43 more tests.The proposed approach effectively detects faults,but a further treatment to the generated tests such as test case prioritization should be done to increase the effectiveness and efficiency of testing.

An approach to formalizing specification-based class testing

This paper presents a framework that can be used to formalize the specification-based single-class test generation process. Object-Z is used to describe both software requirements and the proposed framework. Using this framework, test engineers can automatically get the testing process model during the test generation process. With this model, properties of test cases （ such as relationship between test cases and methods can easily be captured. Furthermore, with the framework, the test process model can be updated automatically with the test generation process. The properties of test cases can then be updated correspondingly. It will greatly facilitate the regression testing. The main contribution of this paper is that it provides an approach to formalizing testing process by extending existing framework to class testing, and a way to represent test cases as multi-part, multi-step, multi-level artifacts.

FPGA-Based High-Frequency Digital Pulse Width Modulator Architecture for DC-DC Converters

Digital pulse width modulator is an integral part in digitally controlled Direct Current to Direct Current (DC-DC) converter utilized in modern portable devices. This paper presents a new Digital Pulse Width Modulator (DPWM) architecture for DC-DC converter using mealy finite state machine with gray code encoding scheme and one hot encoding method to derive the variable duty cycle Pulse Width Modulation (PWM) signal without varying the clock frequency. To verify the proposed DPWM technique, the architecture with control input of six, five and four bits are implemented and the maximum operating frequency along with power consumption results is obtained for different Field Programmable Gate Array (FPGA) devices. The post layout timing results are presented showing that architecture can work with maximum frequency of 326 MHz and derive PWM signal of 3.59 MHz. Experimental results show the implementation of the proposed architecture in low-cost FPGA (Spartan 3A) with on-board oscillator clock frequency of 12 MHz which is multiplied internally by two with Digital Clock Manager (DCM) and derive the PWM signal of 1.5 MHz with a time resolution of 1 ps.

FSM Based DFS Link for Network on Chip

As low power consumption is the main design issue involved in a network on chip (NoC), researchers are concentrating more on both algorithms and architectural approaches. The conventional Dynamic Frequency Scaling (DFS) and history based Frequency Scaling (HDFS) algorithms are utilized to process the energy constrained data traffic. However, these conventional algorithms achieve higher energy efficiencies, and they result in performance degradation due to the auxiliary latency between clock domains. In this paper, we present a variable power optimization interface for NoC using a Finite State Machine (FSM) approach to attain better performance improvement. The parameters are estimated using 45 nm TSMCCMOS technology. In comparison with DFS system, the evaluation results show that FSM-DFS link achieves 81.55% dynamic power savings on the links in the on-chip network, and 37.5% leakage power savings of the link. Also, this proposed work is evaluated for various performance parameters and compared with conventional work. The simulation results are superior to conventional work.

Semi-valid Fuzz Testing Case Generation for Stateful Network Protocol

Network protocols are divided into stateless and stateful. Stateful network protocols have complex communication interactions and state transitions. However, the existing network protocol fuzzing does not support state transitions very well. This paper focuses on this issue and proposes the Semi-valid Fuzzing for the Stateful Network Protocol （SFSNP）. The SFSNP analyzes protocol interactions and builds an extended finite state machine with a path marker for the network protocol; then it obtains test sequences of the extended finite state machine, and further performs the mutation operation using the semi-valid algorithm for each state transition in the test sequences; finally, it obtains fuzzing sequences. Moreover, because different test sequences may have the same state transitions, the SFSNP uses the state transition marking algorithm to reduce redundant test cases. By using the stateful rule tree of the protocol, the SFSNP extracts the constraints in the protocol specifications to construct semi-valid fuzz testing cases within the sub-protocol domain, and finally forms fuzzing sequences. Experimental results indicate that the SFSNP is reasonably effective at reducing the quantity of generated test cases and improving the quality of fuzz testing cases. The SFSNP can reduce redundancy and shorten testing time.

Multi-state autonomous drilling for lunar exploration

Due to the lack of information of subsurface lunar regolith stratification which varies along depth, the drilling device may encounter lunar soil and lunar rock randomly in the drilling process. To meet the load safety requirements of unmanned sampling mission under limited orbital resources, the control strategy of autonomous drilling should adapt to the indeterminable lunar environments. Based on the analysis of two types of typical drilling media （i.e., lunar soil and lunar rock）, this paper proposes a multi-state control strategy for autonomous lunar drilling. To represent the working circumstances in the lunar subsurface and reduce the complexity of the control algo- rithm, lunar drilling process was categorized into three drilling states： the interface detection, initi- ation of drilling parameters for recognition and drilling medium recognition. Support vector machine （SVM） and continuous wavelet transform were employed for the online recognition of drilling media and interface, respectively. Finite state machine was utilized to control the transition among different drilling states. To verify the effectiveness of the multi-state control strategy, drilling experiments were implemented with multi-layered drilling media constructed by lunar soil simulant and lunar rock simulant. The results reveal that the multi-state control method is capable of detecting drilling state variation and adjusting drilling parameters timely under vibration interferences. The multi-state control method provides a feasible reference for the control of extraterrestrial autonomous drilling.

Low Power State Assignment Algorithm for FSMs Considering Peak Current Optimization

Finite state machine （FSM） plays a vital current which is drawn by state transitions can result in role in the sequential logic design. In an FSM, the high peak large voltage drop and electromigration which significantly affect circuit reliability. Several published papers show that the peak current can be reduced by post-optimization schemes or Boolean satisfiability （SAT）-based formulations. However, those methods of reducing the peak current either increase the overall power dissipation or are not efficient. This paper has proposed a low power state assignment algorithm with upper bound peak current constraints. First the peak current constraints are weighted into the objective function by Lagrangian relaxation technique with Lagrangian multipliers to penalize the violation. Second, Lagrangian sub-problems are solved by a genetic algorithm with Lagrangian multipliers updated by the subgradient optimization method. Finally, a heuristic algorithm determines the upper bound of the peak current, and achieves optimization between peak current and switching power. Experimental results of International Workshop on Logic and Synthesis （IWLS） 1993 benchmark suites show that the proposed method can achieve up to 45.27% reduction of peak current, 6.31% reduction of switching power, and significant reduction of run time compared with previously published results.