Method for bounded model checking of interrupt-driven system based on partial order reduction

A technology for driving systems and model checking, applied in the field of partial order optimization, can solve problems such as state space growth, and achieve the effects of reducing intermediate state generation, reducing the number of states, and improving traversal efficiency

Active Publication Date: 2015-04-08
NANJING UNIV
View PDF4 Cites 4 Cited by
  • Summary
  • Abstract
  • Description
  • Claims
  • Application Information

AI Technical Summary

Problems solved by technology

Since the total number of permutations has a factorial relationship with the base number, when the number of interrupts is large, the number of interrupts (that is, the base number) that may simultaneously satisfy the trigger condition in each global state is also large, resulting in an explosive growth of the state space

Method used

the structure of the environmentally friendly knitted fabric provided by the present invention; figure 2 Flow chart of the yarn wrapping machine for environmentally friendly knitted fabrics and storage devices; image 3 Is the parameter map of the yarn covering machine
View more

Image

Smart Image Click on the blue labels to locate them in the text.
Viewing Examples
Smart Image
  • Method for bounded model checking of interrupt-driven system based on partial order reduction
  • Method for bounded model checking of interrupt-driven system based on partial order reduction
  • Method for bounded model checking of interrupt-driven system based on partial order reduction

Examples

Experimental program
Comparison scheme
Effect test

Embodiment Construction

[0029] 1. Architecture

[0030] 1. Interrupt-driven system model

[0031] An interrupt-driven system is a real-time system composed of system tasks and interrupt handlers. There are four types of behaviors in the system: system task scheduling and processing, interrupt triggering and processing. We use timed automata to model system task scheduling and interrupt triggering events, and use pseudocode to model handlers.

[0032] For a timed automaton TA:=0 , C, E, β>, we let β be the mapping from E to interrupt event, when TA departs from state l and passes edge e to state l’ (ie ), the interrupt event corresponding to e is triggered. In the model, the timed automata corresponding to each interrupt or system task run in parallel to form a timed automaton network TANet. System tasks and interrupt handlers are abstracted as a pseudo-code model Proc, which is used to describe the processing of system tasks and interrupt handlers. In order to simulate the whole process, the mod...

the structure of the environmentally friendly knitted fabric provided by the present invention; figure 2 Flow chart of the yarn wrapping machine for environmentally friendly knitted fabrics and storage devices; image 3 Is the parameter map of the yarn covering machine
Login to view more

PUM

No PUM Login to view more

Abstract

Provided is a method for bounded model checking of an interrupt-driven system based on partial order reduction. According to the method, the partial order reduction is adopted to reduce paths and states in the bounded model checking state traversing process of the interrupt-driven system. According to the properties of the interrupt-driven system, first dependency relations between interrupt handling routines are defined; interdependence relations between the interrupt handling routines are obtained through static analysis and expressed with a matrix; finally, in the state space traversing process, when in a global state, a plurality of interrupts simultaneously meet the trigger conditions, and the interrupts generate a partial order path according to the interdependence relations and are executed to a new global state according to the path. The purpose of the method is to omit redundant traversing paths, reduce a state space and shorten verification time. The method has wide applicability, can greatly reduce model test time of the interrupt-driven system and is suitable for the interrupt-driven system comprising a large number of interrupts.

Description

technical field [0001] The invention relates to a partial order optimization technology for bounded model inspection of an interrupt-driven system, which mainly uses the partial order reduction technology to eliminate redundant paths in the model state traversal process, reduce the number of states in the state space, and shorten the search time, belonging to bounded The field of algorithmic optimization for model checking. Background technique [0002] Interrupt-driven system (interrupt-driven system) is a kind of real-time system composed of system tasks and interrupt handlers. In real life, interrupt-driven systems are widely used in safety-critical systems, such as medical assistance systems, rail traffic control systems, and aerospace control systems. Therefore, the correctness guarantee of the system has a particularly important practical significance. However, the occurrence time and sequence of interrupt events are highly uncertain. Different interrupt triggering t...

Claims

the structure of the environmentally friendly knitted fabric provided by the present invention; figure 2 Flow chart of the yarn wrapping machine for environmentally friendly knitted fabrics and storage devices; image 3 Is the parameter map of the yarn covering machine
Login to view more

Application Information

Patent Timeline
no application Login to view more
IPC IPC(8): G06F9/48
Inventor 赵建华蔡增科戎挺
Owner NANJING UNIV
Who we serve
  • R&D Engineer
  • R&D Manager
  • IP Professional
Why Eureka
  • Industry Leading Data Capabilities
  • Powerful AI technology
  • Patent DNA Extraction
Social media
Try Eureka
PatSnap group products

Browse by: Latest US Patents, China's latest patents, Technical Efficacy Thesaurus, Application Domain, Technology Topic.

© 2024 PatSnap. All rights reserved.Legal|Privacy policy|Modern Slavery Act Transparency Statement|Sitemap