Dissertation > Excellent graduate degree dissertation topics show

The Design and Implementation of Program Verification Tools Base on Invariants

Author: TianFeng
Tutor: DengShengLan
School: National University of Defense Science and Technology
Course: Computer technology
Keywords: termination safety invariants optimization problem complexity bound
CLC: TP311.11
Type: Master's thesis
Year: 2011
Downloads: 21
Quote: 0
Read: Download Dissertation

Abstract


With the rapid development of computer science, software plays an increasingly important role in people’s daily life, so the correctness verification of software program got a great deal attention in academic domain. Termination and safety verification are two important parts of program correctness verification, based on Mathematica and generation of invariant, we design and implement a tool for termination and safety verification. The main contributions are summarized as follows:1. The implementation of automatic program invariants generation. Based on Mathematica, we have designed and implemented a tool for automatic program invariant generation, which constructs the linear invariants using CILinear and constructs the polynomial loop invaraints using Aligator. The constructed invariants describe the relationships among the loop program variables, and provide the computation basis for the program correctness verification.2. The implementation of termination verification. First we instrument a counter into program loop to record loop times. Then constructed invariant sets as constraint system and whether counter have minimum as objective function, we transform the termination verification problem into an optimization problem, based on the optimization problem-solving function Minimize in Mathematica, we can not only effectively complete the termination verification, but also generate the exact complexity bound of program loops.3. The implementation of safety verification. First we instrument the assume and statements, establish the propositions for safety verification, construct the verification conditions with the set of invariants, transform the verification of safety into the verification of the validity of the logic formula that the invariants imply the the propositions characterizing safety. Then based on the theorem prover PCS in Theorema, the logical formula can be constructed from a set of invariants implying a formula which specifies the safety property. We can effectively implement the safety verification of program.

Related Dissertations

  1. The Research of Mountain Outdoor Sports Base Construction in Zhejiang Daming Mountain Scenic,G895
  2. Study on Navigation Safety of Towing Drilling Platform in the Harbor,TE951
  3. The Safety Management Research of R Construction Project Based on PDCA,TU714
  4. Research of Companies’ Construction Safety Management,TU714
  5. The Design of the Coal Mine’s Safety Evaluation System Based on Wavelet Neural Network,TD79
  6. Coal miners and practice unsafe behavior measurement,X936
  7. Enterprise Security Benefit Evaluation and Development Strategies,F272;F224.5
  8. Study of the security obligations of the property services company,D923
  9. Project Management of the Visual Education of the Safety Accidents of BF,F426.31
  10. The Research of Construction Engineering Safety Accident Losses Assessment,TU714
  11. Research on Our Country’s Financial Safety under the Background of Financial Globalization,F832
  12. On the responsibility of food safety laws,F203
  13. Decision Support System of Safety Management for Workover Operation,TE938
  14. Safety Supervision Work of Standardization Research,TU714
  15. A Study on the Supervision System of Food Safety in Guangdong Province,F203
  16. Development and Application on Municipal Production Safety Emergency Platform,X922.2
  17. Research of Work Safety Supervision Model of Guangdong Province in Economic Transition Period,X922.2
  18. Problems and Countermeasures about China’s Import and Export Food Safety,F752.6
  19. Food Security Crime Control,D924.3
  20. Quality Assessment of the Real-time Optical Measurement Data in Range Based on the Fuzzy Synthetic Evaluation,TJ06
  21. Study on Virtual Simulation Technology of Safety Valves Based on SolidWorks,TH134

CLC: > Industrial Technology > Automation technology,computer technology > Computing technology,computer technology > Computer software > Program design,software engineering > Programming > Programming method
© 2012 www.DissertationTopic.Net  Mobile