Modified Condition/Decision Coverage based on Jumps

Can the fulfillment of the Modified Condition/Decision Coverage (MD/DC) criteria be checked purely based on the jumps performed by the CPU running the System under Test (SuT)? The thesis should address this question on a theoretical level by analyzing how modern compilers translate C code to object code, as well as on a practical level by implementing the check using existing hardware tools.

Modified Condition/Decision Coverage

In aviation software development the Radio Technical Commission for Aeronautics (RTCA) requires MC/DC. In DO-178C [4] the RTCA defines Modified condition/decision coverage as follows: „Every point of entry and exit in the program has been invoked at least once, every condition in a decision in the program has taken all possible outcomes at least once, every decision in the program has taken all possible outcomes at least once, and each condition in a decision has been shown to independently affect that decision's outcome.“ (see [1,2])

Jumps in the Object Code

C code is compiled to object code which is then executed in the target CPU. By the term object code we mean a sequence of assembler instructions. An if statement in the code will be typically compiled to test instructions followed by conditional jumps. In the COEMS project we are working on runtime verification for CPUs: We are developing a runtime verification hard- and software framework, which analyzes the execution trace of a running CPU without interfering with the program running on the CPU. With this framework we can retrieve the sequence of jumps taken during the program execution.

The Problem

MC/DC is defined on the source code level. According to the CAST, the coverage can be checked on the object code level, if \enquote{the coverage analysis at the object code level and source code level provide the same level of assurance} [3]. As not every if statement is translated exactly the same, especially with compiler optimization turned on, this is not an easy task to assure: The compiler might replace if statements or introduce additional jump tables.

Goals

• Analyze under which circumstances MC/DC can be derived from the observed sequence of jumps performed in the CPU.
• Implement the MC/DC analysis using our hardware tools in close collaboration with our industry partner Accemic.

Requirements

• You have a good knowledge of software engineering and especially testing.
• You have first knowledge or are at least very interested in how modern compilers translate C code into object code.
• You are not afraid of manually analyzing low level source and assembler code.

COEMS

The COEMS project is a European project with international academic and industrial partners from Norway, Romania, Austria and Germany. This thesis can be done in combination with an ERASMUS stay in Norway.

Literature

[1] K. J. Hayhurst, D. S. Veerhusen, J. J. Chilenski, and L. K. Rierson, A Practical Tutorial on Modified Condition/Decision Coverage, NASA/TM-2001-210876
[2] Leanna Rierson, Developing Safety-Critical Software: A Practical Guide for Aviation Software and DO-178C Compliance, 2013, CRC Press
[3] Certification Authoroties Software Team (CAST), Structural Coverage of Object Code, Position Paper CAST-17, Revision 3, 2003
[4] Radio Technical Commission for Aeronautics (RTCA), Software Considerations in Airborne Systems and Equipment Certification, DO-178C