Looking for breakthrough ideas for innovation challenges? Try Patsnap Eureka!

An Outage Verification Method Based on Weighted Pushdown System

A verification method and algorithm technology, applied in multi-programming devices, program control design, instruments, etc., can solve the problems of inability to use the same method to verify interruption, interruption time automata state explosion, etc., to improve reliability and robustness. Great, cost-saving effect

Active Publication Date: 2018-09-18
上海丰蕾信息科技有限公司
View PDF3 Cites 0 Cited by
  • Summary
  • Abstract
  • Description
  • Claims
  • Application Information

AI Technical Summary

Problems solved by technology

[0003] At present, there are some verification methods for this problem at home and abroad, but the same method cannot be used to verify important issues related to interrupts. For example, using Interrupt Timed Automata (Interrupt Timed Automata, ITA) to describe a multi-tasking system with interrupts, the The real-time system is transformed into an interruption-time automaton, and the reachability analysis of ITA is used to verify whether the system satisfies certain or several properties. Question: The control flow graph with color is used to statically check the interrupt-driven software, which mainly analyzes the length and type of the stack and the deadline of execution time

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
  • An Outage Verification Method Based on Weighted Pushdown System
  • An Outage Verification Method Based on Weighted Pushdown System
  • An Outage Verification Method Based on Weighted Pushdown System

Examples

Experimental program
Comparison scheme
Effect test

Embodiment 1

[0080] This embodiment takes the application of the interrupt verification method based on the weighted pushdown system of the present invention to verify the timeout problem of the target code as an example.

[0081] Figure 5 It is a framework diagram for verifying the overtime problem by applying the interrupt verification method based on the weighted push-down system of the present invention. The specific steps of verification are:

[0082] 1. According to the target code that needs to be verified, convert it into an interprocedural control flow graph (Interprocedural Control Graph, ICFG);

[0083] 2. Find the minimum upper bound of each cycle in ICFG, when converted to WPDS, the weight of the minimum upper bound of the cycle operation;

[0084] 3. According to the target code that needs to be verified, its instruction cycle is used as the weight, and the bounded idempotent semi-ring

[0085] operator Defined as taking the minimum value, the operator Defined as ar...

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

The invention discloses an interrupt verification method based on a weighted pushdown system. The method comprises the following steps of firstly, modeling the weighted pushdown system according to instruction jumping relationship in a program target code; then, obtaining all reachable layouts through a reachable algorithm of the weighted pushdown system; traversing all of the obtained reachable layouts; judging whether current layout information meets the requirement or not; if not, judging mistake types and returning mistake paths; if no mistake is discovered after all of the reachable layouts are traversed, returning correct. The method provided by the invention has the advantages that the interrupt verification of a real-time system is combined with the weighted pushdown system; a formalization mode is used for verifying the real-time system interrupt; the verification reliability and robustness are improved; sequential logic relevant to the interrupt, priority inversion, memory access conflict and the time-out problem can be verified at the same time under the same model; the efficiency is high; meanwhile, the cost is also reduced.

Description

technical field [0001] The invention belongs to the field of program static analysis and model inspection, and relates to an interruption verification technology based on a weighted push-down system. Background technique [0002] With the rapid development of computers and mobile Internet, embedded real-time systems are widely used in various industries: various industries such as manufacturing, medical treatment, transportation and communication are closely related to embedded real-time systems. Compared with ordinary computer systems, embedded real-time systems have higher requirements for reliability, especially when a real-time system is applied in a field related to life, any unreliable factors or some strong real-time tasks exceeding the specified time limit may cause difficulties. predicted serious consequences. In the embedded real-time system, in order to enable the system to interact with the external environment in a timely manner, people have introduced an "inte...

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
Patent Type & Authority Patents(China)
IPC IPC(8): G06F9/48
CPCG06F9/4831
Inventor 黄滟鸿郭欣史建琦何积丰李昂方徽星
Owner 上海丰蕾信息科技有限公司
Who we serve
  • R&D Engineer
  • R&D Manager
  • IP Professional
Why Patsnap Eureka
  • Industry Leading Data Capabilities
  • Powerful AI technology
  • Patent DNA Extraction
Social media
Patsnap Eureka Blog
Learn More
PatSnap group products