Hostname: page-component-cd9895bd7-7cvxr Total loading time: 0 Render date: 2024-12-26T18:56:32.672Z Has data issue: false hasContentIssue false
  • English
  • Français

TCAS software verification using constraint programming

Published online by Cambridge University Press:  26 July 2012

Arnaud Gotlieb
Arnaud Gotlieb*
Affiliation:
INRIA – Rennes – Bretagne Atlantique, 35042 Rennes Cedex, France; e-mail: [email protected] Certus Software V&V Centre, Simula Research Laboratory, Lysaker, Norway; e-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

Safety-critical software must be thoroughly verified before being exploited in commercial applications. In particular, any TCAS (Traffic Alert and Collision Avoidance System) implementation must be verified against safety properties extracted from the anti-collision theory that regulates the controlled airspace. This verification step is currently realized with manual code reviews and testing. In our work, we explore the capabilities of Constraint Programming for automated software verification and testing. We built a dedicated constraint solving procedure that combines constraint propagation with Linear Programming to solve conditional disjunctive constraint systems over bounded integers extracted from computer programs and safety properties. An experience we made on verifying a publicly available TCAS component implementation against a set of safety-critical properties showed that this approach is viable and efficient.

Type
Articles
Information
The Knowledge Engineering Review , Volume 27 , Special Issue 3: Constraint Programming for Air Traffic Management , 26 July 2012 , pp. 343 - 360
Copyright
Copyright © Cambridge University Press 2012

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Balas, E. 1985. Disjunctive programming and a hierarchy of relaxations for discrete optimization problems. SIAM Journal on Algebraic and Discrete Methods 6(3), 466–486.CrossRefGoogle Scholar
Bicevskis, J., Borzovs, J., Straujums, U., Zarins, A., Miller, E. 1979. SMOTL—a system to construct samples for data processing program debugging. IEEE Transactions on Software Engineering 5(1), 60–66.CrossRefGoogle Scholar
Botella, B., Gotlieb, A., Michel, C. 2006. Symbolic execution of floating-point computations. The Software Testing, Verification and Reliability Journal 16(2), 97–121.CrossRefGoogle Scholar
Brandis, M. M., Mössenböck, H. 1994. Single-pass generation of static single-assignment form for structured languages. ACM Transactions on Programming Languages and Systems 16(6), 1684–1698.CrossRefGoogle Scholar
Brummayer, R., Biere, A. 2007. C32SAT: checking C expressions. In Proceedings of the 19th International Conference on Computer Aided Verification (CAV'07), Lecture Notes in Computer Science, 4590, 294–297. Springer.CrossRefGoogle Scholar
Carlsson, M., Ottosson, G., Carlson, B. 1997. An open-ended finite domain constraint solver. In Proceedings of the Programming Languages: Implementations, Logics, and Programs. Lecturer Notes in Computer Science, 1292, 191–206. Springer, Southampton, UK.CrossRefGoogle Scholar
Chaki, S., Clarke, E., Groce, A., Jha, S., Veith, H. 2004. Modular verification of software components in C. IEEE Transactions on Software Engineering (TSE) 30(6), 388–402.CrossRefGoogle Scholar
Clarke, E., Kroening, D. 2003. Hardware verification using ANSI-C programs as a reference. In Proceedings of the ASP-DAC'03, 308–311. Kitakyushu, Japan.CrossRefGoogle Scholar
Coen-Porisini, A., Denaro, G., Ghezzi, C., Pezze, M. 2001. Using symbolic execution for verifying safety-critical systems. In Proceedings of the European Software Engineering Conference (ESEC/FSE'01), ACM, 142–150.Google Scholar
Collavizza, H., Rueher, M. 2006. Exploration of the capabilities of constraint programming for software verification. In Tools and Algorithms for the Construction and Analysis of Systems (TACAS'06), 182–196. Springer, Vienna, Austria.CrossRefGoogle Scholar
Collavizza, H., Rueher, M., Van Hentenryck, P. 2008. CPBPV: a constraint-programming framework for bounded program verification. In Proceedings of CP2008, Lecture Notes in Computer Science, 5202, 327–341. Springer.CrossRefGoogle Scholar
DeMillo, R. A., Offut, J. A. 1991. Constraint-based automatic test data generation. IEEE Transactions on Software Engineering 17(9), 900–910.CrossRefGoogle Scholar
Denmat, T., Gotlieb, A., Ducasse, M. 2007a. An abstract interpretation based combinator for modeling while loops in constraint programming. In Proceedings of Principles and Practices of Constraint Programming (CP'07), Lecture Notes in Computer Science, 4741, 241–255. Springer Verlag.Google Scholar
Denmat, T., Gotlieb, A., Ducasse, M. 2007b. Improving constraint-based testing with dynamic linear relaxations. In Proceedings of the 18th IEEE International Symposium on Software Reliability Engineering (ISSRE’ 2007), Trollhättan, Sweden.CrossRefGoogle Scholar
Do, H., Elbaum, S. G., Rothermel, G. 2005. Supporting controlled experimentation with testing techniques: an infrastructure and its potential impact. Empirical Software Engineering: An International Journal 10(4), 405–435.CrossRefGoogle Scholar
DO-178B/ED-12B. 1992. Software Considerations in Airborn Systems and Equipment Certification, RTCA and EUROCAE. Inc Washington, DC, USA and EUROCAE, Paris, France.Google Scholar
Godefroid, P., Klarlund, N., Sen, K. 2005. Dart: directed automated random testing. In Proceedings of the PLDI'05, 213–223. Chicago, IL, USA.CrossRefGoogle Scholar
Gotlieb, A. 2009. Euclide: a constraint-based testing platform for critical C programs. In 2nd International Conference on Software Testing, Validation and Verification (ICST'09), Denver, CO.Google Scholar
Gotlieb, A., Botella, B., Rueher, M. 2000. A CLP framework for computing structural test data. In Proceedings of Computational Logic (CL'2000), London, UK, Lecture Notes in Artificial Intelligence, 1891, 399–413.Google Scholar
Gotlieb, A., Denmat, T., Botella, B. 2007. Goal-oriented test data generation for pointer programs. Information and Software Technology 49(9–10), 1030–1044.Google Scholar
Henzinger, T., Jhala, R., Majumdar, R., Sutre, G. 2003. Software verification with blast. In Proceedings of the 10th Workshop on Model Checking of Software (SPIN), 235–239. Portland, OR, USA.CrossRefGoogle Scholar
Hooker, J., Erlender, G. O., Thorsteinsson, S., Kim, H.-J. 2000. A scheme for unifying optimization and constraint satisfaction methods. The Knowledge Engineering Review 15(1), 11–30.CrossRefGoogle Scholar
Holzbaur, C. 1995. OFAI clp(q,r) Manual, 1.3.3 edition. Austrian Research Institute for Artificial Intelligence.Google Scholar
Lebbah, Y., Michel, C., Rueher, M. 2005. A rigorous global filtering algorithm for quadratic constraints. Constraints Journal 10(1), 47–65.CrossRefGoogle Scholar
Livadas, C., Lygeros, J., Lynch, N. A. 1999. High-level modeling and analysis of TCAS. In IEEE Real-Time Systems Symposium, 115–125. Phoenix, AZ, USA.Google Scholar
McCormick, G. P. 1976. Computability of global solutions to factorable nonconvex programs: Part 1—convex underestimating problems. Mathematical Programming 10, 147–175.CrossRefGoogle Scholar
Milano, M., Ottosson, G., Refalo, P., Thorsteinsson, E. S. 2002. The role of integer programming techniques in constraint programming's global constraints. Informs Journal on Computing 14(4), 387–402.CrossRefGoogle Scholar
Neumaier, A., Shcherbina, O. 2004. Safe bounds in linear and mixed-integer linear programming. Mathematical Programming: Series A and B Archive 99(2).CrossRefGoogle Scholar
Offut, J. A., Jin, Z., Pan, J. 1999. The dynamic domain reduction procedure for test data generation. Software—Practice and Experience 29(2), 167–193.3.0.CO;2-V>CrossRefGoogle Scholar
Randimbivololona, F. 2001. Orientations in Verification Engineering of Avionics Software. In Informatics, 10 Years Back, 10 Years Ahead, Reinhard Wilhelm. Lecture Notes in Computer Science 2000, 131–137. Springer.Google Scholar
Refalo, P. 1999. Tight cooperation and its application in piecewise linear optimization. In Proceedings of CP'99, Alexandria, Virginia.CrossRefGoogle Scholar
Rossi, F., van Beek, P., Walsh, T. (eds). 2006. Handbook of Constraint Programming. Elsevier.Google Scholar
Sankaranarayanan, S., Colòn, M. A., Sipma, H., Manna, Z. 2006. Efficient strongly relational polyhedral analysis. In Proceedings of VMCAI'06, 115–125. Charleston, SC, USA.CrossRefGoogle Scholar
Sen, K., Marinov, D., Agha, G. 2005. CUTE: a concolic unit testing engine for C. In Proceedings of ESEC/FSE-13, ACM Press, 263–272.Google Scholar
U.S. Department of Transportation Federal Aviation Administration 2000. Introduction to TCAS II —version 7.Google Scholar
Williams, N., Marre, B., Mouy, P., Roger, M. 2005. PathCrawler: automatic generation of path tests by combining static and dynamic analysis. In Proceedings of Dependable Computing—EDCC'05, 281–292. Budapest, Hungary.CrossRefGoogle Scholar