Zoë Stephenson

Tim Kelly

Jean-Louis Camus

Developing an Argument for Def Stan 00-56 from Existing Qualification Evidence

Keywords: Certification, hazard analysis, safety case, argumentation

Commonly-used civil guidance and standards in the safety-critical software industry (IEC 61508, EN 50128, DO-178B) constrain development activity and generate process and product evidence. However, procurements for UK defence systems must be supported with a safety case assessed against Def Stan 00-56 Issue 4. This paper studies the use of evidence from civil guidance and standards in arguments towards DS 00-56. The approach is centred on a particular application, the KCG qualified code generator, and is based on a generic software contribution argumentation approach. The results show that issues arise in substantiating failure conditions, choosing a suitable level of detail in the argument and relating detailed explanations to the structure of the evidence. Explicit argumentation was found to be useful in addressing each of these issues.

Introduction

Every industry is governed by a body of standards, and the safety-critical software industry is no different. Commonly-used standards include IEC 61508 [START_REF]Functional safety of electrical/ electronic/ programmable electronic safety-related systems[END_REF], EN 50128 [START_REF]Railway applications. Communications, signalling and processing systems. Software for railway control and protection systems[END_REF] and DO-178B [START_REF]Software Considerations in Airborne Systems and Equipment Certification[END_REF]. These standards recommend particular activities that contribute towards the safety of a product under development. Examples of these activities include hazard analysis, failure modes and effects analysis, configuration control, traceability and test coverage analysis. Documentation of these activities and their results is submitted for independent assessment against the requirements or objectives of the standard. When the product under development is not a complete system -such as a component, a service layer, an operating system or a development tool -it is common to assess the product against the needs of many different safety standards. The commercial benefit of this extra effort is the ability to offer the product to customers in different sectors, and the standards are similar enough that there is a great deal of overlap in the evidence produced. For products that are used in safety-critical systems procured by the UK Ministry of Defence, assessment against Def Stan 00-56 [START_REF] Ministry | Safety Management Requirements for Defence Systems[END_REF] is required. This is a different style of standard to those described above; instead of recommending activities, it requires that particular goals are achieved and that the safety of the product is argued in a separate safety case. This shift in approach means that it is not appropriate to simply reuse qualification evidence. However, matching up the structure of a compelling and defensible argument with the body of existing evidence is not straightforward. To help address this problem, we are customising a generic argument approach [START_REF] Menon | Interim Standard of Best Practice on Software in the Context of DS 00-56 Issue 4[END_REF] to create guidance for users of the socalled "Esterel SCADE certification factory", involving SCADE Suite tools, in particular the KCG qualified code generator. Section 2 describes the operation of the KCG qualified code generator in more detail, to serve as background for the discussion. In section 3, we describe the structure of an assurance case to support the use of such tools. The experience from development of this assurance case is expanded in section 4, identifying the key issues and the strategies taken to address them, particularly in terms of the benefits of explicit argumentation. Related work is briefly studied in section 5 and conclusions are given in section 6.

KCG qualified code generator

The SCADE suite provides graphical and textual modelling capabilities for control algorithms, with an emphasis on well-defined, unambiguous behaviours based on formal semantics. The KCG tool converts a SCADE model into an equivalent program in the C language, ready for integration with user-supplied I/O and scheduling code. To support the assertion that the resulting object code has the same behaviour as the SCADE model, there are several Conditions of Use that the user must follow, for example:

 The model (and the underlying formal system) assumes that processing is much quicker than input/output interaction, and uses a model of instantaneous computation of outputs from inputs at each processing step. The C implementation only satisfies this assumption if the worst-case execution time of the code is less than the iteration rate of the model and the software.

 The generated C code is trusted, but the compiler must also be trusted to produce a correct output. Evidence to support this must be generated by the user for the particular toolchain for their target platform. The code generator generates only a very limited range of C constructs, so a test suite to test those constructs is feasible and a ready-made test suite of this kind is available with the code generator.

Assurance case structure

The overall assurance case is structured into a number of parts, as shown in Figure 1:

 An argument that shows that the KCG tool itself was developed in an appropriate way. For example, this argument includes details of regular reviews, personnel competence and the hazard identification process.

 An argument that shows that the KCG tool correctly transforms input to output -that the resulting object code has the same behaviour as that specified in the model. This refers to the KCG development argument.

 An argument to show that the development of KCG adequately meets the objectives of DD 00-56.

 A set of custom argument patterns for users of the KCG tool. The patterns show how to link the above three arguments into a software contribution argument for the user's own software system, which in turn should be linked to the safety case for the system into which the software is ultimately integrated.

Each part of the assurance case has its own purpose. This structure helps with development and review of the individual arguments, as well as managing the complexity of the argument.

Goal structuring

The argument was developed in a top-down fashion using the Goal Structuring Notation (GSN). GSN is a graphical notation for the representation of structured argument. The main graphical elements of the notation are shown in Figure 2. With a GSN structure, there is a top-level claim, a goal, the truth of which the writer wishes to convince the reader. The supporting elements describe the shape of the argument, which is carried in the text labels and in further discursive material. The argument eventually reaches assumptions, justifications and solutions that collectively form the evidence on which the argument is based.

Goal

Strategy

Assumption

A

Goals represent the claims that are made in the argument. The whole argument exists to convince the reader of the truth of its topmost goal.

Context

Strategies show explicitly the approach taken to link goals to supporting discussion and evidence. When the argument step is trivial, the strategy may be omitted.

Assumptions give additional constraints on the argument, to show the basis on which claims are made.

Context provides further definition to the argument, explaining key points in more detail. Contextual elements are important as they show the reader that a particular definition or model is in use.

The "is solved by" link shows the main flow of the argument from topmost goal down to evidence. Solution Solutions represent basic evidence artefacts that are used in direct support of a goal. The link from goal to solution should be obvious.

The "in context of" link provides contextual links to constrain the scope of an element. 1 shows these public goals along with their instantiation for the KCG assurance case and corresponding comments on suitability.

For the evidence supporting KCG, the most appropriate choice was that with the most specific scope. The higher-level goals identified in the pattern are then the responsibility of the tool user. The explicit GSN structure brings an additional benefit in demonstrating to the tool user and to other stakeholders exactly the type of claim being made and how this claim relates to its surrounding claims.

Argument over sources of deviation

Issue: The pattern-based argument is centred on sources of deviation of the generated C code from the input SCADE model, but no advice is given with the pattern on the process of identifying deviations. Approach: Several existing development documents contained expert analysis of potential failure conditions using architectural models and systematic analysis. To substantiate the claim that the failure conditions have been correctly identified, a separate analysis was conducted and the results were compared to the original findings to confirm that independent analyses end up with the same results.

To create this view of the possible sources of deviation, a three-step process was used:

 KCG architectural documentation was consulted to produce a data-flow architectural model of KCG. The model was also informed by discussions with KCG developers, to ensure that an appropriate level of detail was represented. The data-flow style is particularly appropriate for KCG because of its focus on transforming one representation of behaviour to another. A dedicated gap analysis was conducted in these areas to identify the platform gaps and their overall effect. For example, SCADE semantics assume instantaneous execution of the code compared to the iteration rate of the control loop, whereas the eventual object code has some non-zero execution time. It is therefore up to the KCG tool user to determine the worst-case execution time of the control loop on the target platform and ensure that this is compatible with the iteration rate. The previous analysis of KCG failure conditions was integrated into these newer analysis results. This process was performed alongside the other steps to ensure that all of the different analyses would fit together. This integration effort prompted the platform gap analysis and also revealed some missing domain knowledge that resulted in an incomplete customisation of the HAZOP guide words.

Presentation of analysis results

Issue: The HAZOP and gap analyses produced a large number of possible failure conditions, but there were many similarities in the conditions and significant similarities across the suggested mitigations. In all, the 68 failure conditions gave rise to 37 individual mitigation actions. Presenting this explicitly according to the pattern structure would lead to a significant replication of information across a complex GSN structure, for which the benefit was unclear. While the underlying argument would be the same in each case, it was important to be able to present the information with a useful amount of detail. Approach: This issue was tackled in six steps:  The failure conditions were classified according to their ability to cause a deviation of the C code behaviour from the model behaviour. A brief analysis of the classification showed that mitigations for the critical failure conditions would also mitigate the non-critical failure conditions. This reduces the number of mitigations that need to be addressed in the argument.

 The available mitigations were collated and grouped into user actions, installer actions and developer actions. Table 3 gives a summary of the mitigation areas. This gives a better picture of the overall scope of mitigations.

 The options for presentation of failure conditions were enumerated: o A single reference in the argument to the full set of failure conditions.

o

A reference to each of the 23 critical failure conditions (those leading to undetected deviation) plus a combined reference to the non-critical failure conditions.

o

A reference to actions grouped according to the 3 responsible agents.

o

A reference to actions grouped according to the 13 mitigation areas.

o

An individual reference to each of the 37 mitigating actions.

 The options for argument structure in this area were sketched out as shown in Table 4. The table gives a crude account of the overall complexity of the graphical structure for different levels of detail in the argument presentation.

 An appropriate combined representation was chosen.

In this case, the argument was structured with the failure conditions grouped together into a single entity and the mitigating actions divided up into the three stakeholder areas. The division into mitigation areas could also have been usable at this level of the argument, although the choice of mitigation areas came relatively late in the course of the project. more problematic, as the tool developer has no control over the tool user. The strongest argument that may be made here is that the tool developer identifies conditions that the user must follow so that the tool output does not deviate from the behaviour specified by the input. When the tool user comes to make claims about the system built using that tool, that user must then demonstrate that these conditions use have been met.

To assist the tool user, the customised software contribution patterns that are available to the KCG tool user identify exactly where this argument should be made.

Traceability supporting completeness

Issue: At several points in the argument, there is a need to demonstrate completeness. In some cases, we found that an appeal could reasonably be made to the traceability relationships in development artefacts. In other cases, while such evidence could be used to support an argument, the evidence had not already been generated as an existing development artefact. In this situation, the benefit of the additional evidence must be traded off against the effort involved in generating the evidence. Approach: There were three points at which traceability was a strong candidate for support of completeness:

 The identification of failure conditions: for this area, we appeal to the traceability from the failure conditions to the data-flow architectural model of the KCG tool, and from the identified failures to the failures obtained from previous domain expert analysis. Issues identified from the traceability structure were fed back into the analysis process and prompted the use of explicit platform gap analysis.

 The combination of mitigations covering failure conditions: here the argument must show that developer, installer and user mitigation activities are complete with respect to the failure conditions that they address. The argument refers to the traceability from mitigation actions to the failure conditions that they address, but does not call for specific analysis of coverage, as such analysis is trivial with just three types of mitigation activity. If there were many more activity types (or perhaps responsible agents) then an explicit coverage analysis would be appropriate.

 The combination of guidance areas covering the intent of a standard: the top of the KCG development assurance argument is divided into system development guidance areas on the basis of a recognition of system development themes:

o Responsibility assignment: in this area, the organisation must identify appropriate roles and skills, identify the personnel in those roles, and demonstrate that those people have those skills.

o Safety management: here, the process must focus on the analysis of failure conditions and the management of risk. Coverage: this area embodies the idea that 100% of the requirements should be shown to be correctly implemented and no unintended functionality should be present. To show that these areas match with the content of appropriate existing guidance, the argument refers to three areas in which process guidance is already given (DO-178B, CAST-13 and IEC 61508). There is currently no explicit identification of any traceability mapping from the process areas to the contents of those guidance documents and standards. This step in the argument is instead taken to represent best practice and professional judgement. 4.6 Explicit product and process evidence Issue: Some of the evidence produced by following industry guidance will relate to the correctness of the product with respect to its intended behaviour. Other evidence will show that the product was developed competently in accordance with industrial best practice. It is not common to find the distinction made explicit in industry guidance, nor in the evidence so produced, yet the distinction is a basic feature of an explicit argument. Approach: The assurance argument is structured as a product argument that appeals to a process argument (an argument for development assurance). Beneath this structure, one group of evidence relates to the product argument, showing that KCG in itself has the required integrity, while other evidence relates to the process argument, showing the suitability of the development process for a critical development. For example, software unit test reports and analysis of the adequacy of the conditions of use appear in the KCG product argument, while coverage reports and configuration management audits appear in the KCG development process argument. The assurance gained from the process argument provides confidence that appropriate methods were employed in generating the product and the evidence that supports the claim that that product meets its requirements. 4.7 Good practice Issue: In many parts of the argument, the claim is essentially that some evidence is adequately generated. There is no standard approach for linking such a claim to existing evidence. Approach: To identify appropriate evidence, the argument was built with the following four aspects of good practice in mind:

 Definition of a process that is capable of generating the required evidence.

 Assessment of the process definition to show that it is appropriate for the type of evidence being used. For example, in KCG development there is independence between implementation and testing.

 Evidence that the process has been carried out effectively, such as logs or audits.

 Evidence produced by the process itself, such as functional test results or coverage data. In many cases these aspects are distributed around the argument. For the example of functional test results, the four aspects arise as follows:

 The testing process definition is given in the test plans, and these are referenced from the KCG development argument, under goals concerned continual safety consideration throughout the lifecycle.

 Adequacy of the testing process definition is not shown directly, but is established by association with the guidance given in established standards.

 Evidence that testing has been carried out effectively is found in the KCG development process argument, demonstrating 100% requirements coverage and MC/DC.  The actual test evidence is used in the argument structure to substantiate the claim that the safety requirements for the KCG have been met. Assessment of evidence according to these four aspects provided a useful rule of thumb when identifying the role of particular pieces of available evidence. 4.8 Support for complex guidance Issue: When the end user of the KCG tool is producing software that is governed by DS 00-56, some additional guidance will be necessary. To ensure that the guidance is followed, the value of that guidance -or the potential cost of not following that guidance -must also be conveyed to the user. Approach: The argument structure supports this in two ways:  The KCG user is given conditions of use that constrain the installation and use of the tool to the context within which KCG assurance claims are valid. This involves areas such as the operating system used by the tool, command line options and the setting up of optimised operations in the generated code. As a standalone list of conditions, some effort could be involved to track down the rationale for each condition. In the argument structure, the conditions of use trace to installer and user activities that mitigate specific failure conditions, which in turn links to a higher goal involving more general identification, elimination and mitigation of failure conditions. A final step from this point shows that the conditions in question are the critical failure conditions from the hazard analysis and the platform gap analysis. The analysis report classifies the mitigating actions and links them to the conditions of use, completing the picture.

 The KCG user is given guidance on constructing a software safety case. This is based on customised software safety argument patterns, indicating the tiers of development for use of KCG and the links from KCG-specific tiers to the KCG product argument and its supporting material. 4.9 Direct objective mapping Issue: The audience for a safety case is diverse. For some readers, the important information will be the safety argument and the degree to which it convinces the reader of its claim. For other readers, the important information will be the satisfaction of the particulars of DS 00-56. It is difficult to structure a safety case so that it will satisfy a range of different stakeholders. Approach: For the KCG assurance case, a particular structure was used to link that assurance case into the tool user software safety case in a way that allows reference to adherence to a particular standard. The structure is shown in Figure 3. The DS 00-56 conformance argument supports an overall KCG tool dependability claim, which in turn supports a claim that the output of KCG, when compiled and executed on the target platform, accurately implements the SCADE model. This claim provides backing for the assertion that validation in the SCADE environment is sufficient evidence for the correctness of the design tier in the decomposition.

Related work

Argumentation research for safety cases focuses on the abstract concepts and general principles of topdown argument construction. Examples include argumentation patterns [START_REF] Kelly | Safety Case Construction and Reuse Using Patterns[END_REF], safety case modularity [START_REF] Althammer | The DECOS Concept of Generic Safety Cases -A Step Towards Modular Certification[END_REF], assurance sufficiency [START_REF] Hawkins | Software Safety Assurance -What is Sufficient?[END_REF] and argument justification [START_REF] Bishop | The Future of Goal-Based Assurance Cases[END_REF]. Nevertheless, arguments are almost never constructed purely top-down; there is always some notion of the available evidence and the support that it may give to an argument. Working from the evidence to identify appropriate goals may not seem ideal, but it the advantage of focusing on the power of the evidence rather than searching for ways to support an a priori belief, a danger highlighted in the Haddon-Cave report [12, p259, pt 5]. In practice, a combination of top-down principles, patterns and existing evidence will be applied in creating a safety case. While there is little existing research directly related to the use of evidence from one standard in support of another, several parts of this paper are essentially practical examples of more general principles:

 The allocation of evidence between process and product arguments supports the targeted process argument approach of Habli and Kelly [START_REF] Habli | Achieving Integrated Process and Product Safety Arguments[END_REF]. They advocate process arguments that are structured around concerns that are particular to the project, rather than around the general process structure imposed by a standard. For KCG, an intermediate approach was taken in which the process argument stands separately but makes specific claims about areas that attract concern.

 The issue of identifying and obtaining appropriate traceability information is also found in other work [START_REF] Ridderhof | Establishing Evidence for Safety Cases in Automotive Systems -A Case Study[END_REF]. The identification of the need for traceability is similar here, but instead of relying solely on existing traceability information, Ridderhof et al propose tool support to allow for the construction of arbitrary traceability links. They identify automated traceability management as a key issue in the success of such an approach.

Summary and conclusions

Given appropriate evidence, construction of an explicit argument should be straightforward. However, when the argument is made against one standard and the evidence is from another, there is the potential for difficulty in deciding on the argument structure and the exact evidence to include. In producing an assurance argument for the KCG

Figure 2 :

 2 Figure 2: main GSN symbols

o

  An individual reference to each of the 68 failure conditions.  The options for presentation of mitigating actions were enumerated: o A single reference to the full set of mitigating actions.

Figure 2 :

 2 Figure 2: GSN fragment showing mitigation argument structure

  essential as backing for a product argument. o Continuous safety: safety must be addressed before development begins, during development, at the point of deployment and in the context of the use of the tool.oTraceability: strong traceability is vital for support of a product argument.

  o

Figure 3 :

 3 Figure 3: GSN fragment showing argument integration structure

Table 1 :

 1 Instantiation and discussion of potential top-level goals

	Pattern element	Instantiation	Suitability
	Goal: SwSystemSafe:	KCG qualified code generator is	This goal references the
	{software Y} is acceptably safe	acceptably safe to operate	surrounding development process
	to operate within {system Z}	within development process for	operated by the KCG tool user.
		{system Z}	This claim requires additional
			evidence beyond that pertaining to
			KCG.
	Goal: SwContributionAcc: The	The contribution made by the	This goal references the hazards
	contribution made by {software	KCG qualified code generator	in the system for which KCG
	Y} to {system Z} hazards is	to {system Z} hazards is	produces software. Not all of these
	acceptable	acceptable	hazards will relate to software
			behaviour, and very few will relate
			to the behaviour of KCG. The
			scope is still too large to be
			supported by evidence about KCG.
	Goal: Hazard: Software	Goal: Hazard: Software	This goal identifies an argument
	contribution(s) to {Hazard} is	contribution to deviation of C	that is directly concerned with the
	acceptably managed	code behaviour from input	transformation from the input
		SCADE model is acceptably	SCADE model to C code. This
		managed	directly matches the scope of the
			available evidence.

Table 2 :

 2 Customised HAZOP guidewords for KCG architecture analysis

	Guide Word	Translation	Hand-Code	Control	Feedback	Service
	No	The translation	No user-supplied			Nothing	No service is
		simply does not	code is given.				reported about	available.
		take place.							the behaviour
										of the tool.
	Less
	More
	Part Of	Some part of	Not all of the			The feedback	Only some of
		the	SCADE	necessary user-			reports	are	the	required
		model		isn't	supplied code is			missing	services	are
		translated, or	given.					feedback about	available.
		some part of						some part of
		the C code isn't						the process or
		compiled.							the model.
	As Well As	Something		The user supplies			The feedback
		extra is put into	additional code			reports	give
		the C code or	that	is	not			spurious
		the object code	necessary.				additional
		that was not						information.
		intended.
	Reverse									Tool indicates
										opposite
										success.
	Other Than	Translation		User	supplies	The	wrong	The	tool	The	service
		creates			incorrect code.		options	are	indicates	a	operates
		different					given to the	different result	incorrectly.
		behaviour	to				tool.		to the actual
		that of the						result
		model.								obtained.

Table 3 :

 3 Summary of mitigation areas by responsible agent

	User actions	Installer actions	Developer actions
	 Verification of user-	 Verification of correct tool	 100% requirements test
	supplied code, type	and OS version	coverage
	specification, command line and customisation  Validation of correct tool invocation and outcome  Use of the tool on multiple development systems	 Verification command line and file of tool processing capabilities	 Full MC/DC  Absence of unintended functions  Verification of command line and file processing  Analysis of response to resource constraints
	 Verification of post-generation code		 Analysis of underlying OS and library services
	modifications
	 Analysis of object code
	properties

Table 4 :

 4 Complexity indication for detail in failure conditions and mitigations

	Failure Conditions

qualified code generator intended for DS 00-56, we found that we could use a wide range of evidence from the development and analysis of the tool under DO-178B, EN 50128 and IEC 61508. In terms of evidence generation, our efforts were centred on additional support for the claim that sources of deviation were correctly identified. The remaining argument was supported with evidence generated through alternative standards.

The overall argument construction effort revolved around:

 Correctly identifying the relevant topmost goal, by instantiating a list of suggested topmost goals and comparing against the available scope of evidence;

 Presenting the results of hazard analysis in the argument in a manageable way;

 Providing an appropriate link from high-level mitigations to evidence;

 Linking to evidence that demonstrates completeness of analysis;  Dividing existing evidence into process and product evidence;

 Where evidence is presented for a claim about the product, looking for backing evidence to show good practice in the generation of that evidence;

 Providing a route for the identification of rationale behind the guidance given to the tool user;

 Describing the relationship between the available evidence, the supporting arguments and the individual requirements of DS 00-56. While many parts of this work represent instantiations of general principles, we believe there is novelty and value in our approach to finding an appropriate presentation mechanism for a large body of evidence and in the method of scope comparison to document the selection of an appropriate top-level goal.


Adrien Derock

Patrick Hebrard

Frédérique Vallee

Convergence of the Latest Standards Addressing Safety and Security for Information Technology

Keywords: safety, security, convergence

Safety and Security have always been considered separately in most industrial process. Actually, there is a growing consensus that for many applications, Safety as well as Security demands have to be observed in a coherent manner. Risk analysis to counter malicious attacks can be also reused with appropriate modification for unplanned system failure.

Introduction

For numerous years the "Software Safety" and "Information Systems Security" communities have been following their own ways with a few interactions.

This independence emerges when reviewing the standards issued by both communities until 2000-2005. Among them two major standards are well representative of each community:

• "Common Criteria" for Information Technology Security Evaluation [1],

• "ISO 61508" for Functional safety of electrical / electronic / programmable electronic safety-related systems [2].

To roughly summarize the differences between the two approaches described in these two standards, we can say that Information Security Community recommends a combination between "system specification audit" (inheriting from the historical MARION method developed by the CLUSIF in 1983) and "implementation requirement" for security, while functional safety approach is based on an adaptation of usual product risk management techniques associated to process requirements. From their side "usual" product risk management techniques for programmable systems are well defined into the ISO/CEI 15026 standard [4].

This differentiation between security and safety is nowadays becoming unbearable because both aspects are more and more merged in modern complex systems such as Naval System for the particular case of DCNS or in other embedded communication systems (in Nuclear Power Plants for example). This is particularly true for complex system based mostly on software. This convergence is worth to be mentioned and is the subject of this paper. Actually the harmonization of security and safety studies can be a source of productivity improvement for many companies.

The next sections will successively:

• briefly describe the security and safety standards that are examined in this paper, • enlighten the communalities that can be found in both security and safety new standards, • propose a generalised process approach that is consistent with most of the safety and security standards requirements, • conclude by showing which benefits many companies could gain in harmonising their safety and security organisations (through DCNS perspective).

Short description of the selected security and safety standards

ISO 27005 standard

The ISO 27005 is the prime 27000 series standard covering information security risk management. It has been published in June 2008.

This standard provides guidelines for information security risk management (ISRM) in an organization, specifically supporting the general concepts of information security management system specified by ISO 27001.

The ISO 27005 standard does not provide neither recommend a specific methodology. It is up to the organization to define its approach that will depend upon a number of factors, such as the actual scope of the Information Security Management System (ISMS), or the industry/commercial sector. The EBIOS 27005 methodology could be used for this purpose.

[X]

The ISO 27005 standard is based on a risk management approach, i.e. it specifies a structured, systematic and rigorous risk management process from analyzing risks to creating the risk treatment plan.

The information security risk management process consists of:

• Context Establishment: intends to define the risk management's boundary

• Risk Assessment: o Risk Analysis (Risk Identification &
Estimation phases): intends to define the assets, the threats and vulnerabilities and concludes by evaluating the risk level.

o Risk Evaluation: takes into account the objectives of the organization and prioritizes the risks. • Risk Treatment: to reduce, retain, avoid or transfer the risks. • Risk Acceptance: to formally record the decision to accept the residual risks.

In parallel support processes are described, such as:

• Risk Communication: for exchanging and/or sharing information about risk between the decision makers and other stakeholders. • Risk Monitoring and Review: to maintain an overview of the complete risk snapshot.

ISO/IEC 61508 family standards

The Created in European version by CENELEC in 2002 as EN 61508, the IEC 61508 standard has its origins in the process control industry sector. It is intended to be a basic functional safety standard applicable to all kinds of industry. This standard sets out a generic approach for all safety lifecycle activities for systems comprised of electrical and/or electronic and/or programmable electronic components (electrical/electronic/ programmable electronic systems (E/E/PESs)) that are used to perform safety functions. Functional safety is defined in the IEC 61508 standard as: "part of the overall safety relating to the EUC (Equipment Under Control) and the EUC control system which depends on the correct functioning of the E/E/PE safety-related systems, other technology safety-related systems and external risk reduction facilities." The safety lifecycle described in the standard covers all activities needed for an E/E/PES system development and use, going from initial design until decommissioning through development, installation, and operation phases. The safety approach is based on risk prevention and the system SIL (Safety Integrity Level) determination classified on a 4 degrees scale going from SL1 (the less critical) to SIL4 (the most critical).

For the 2 more critical levels (SIL 3 and SIL4), the standard is very stringent regarding the number and variety of techniques that must be applied. Moreover these techniques are not always consistent and often very costly to operate in usual industrial contexts. When the system is not a pure safety system (i.e. implementing a "safety" dedicated function such as "nuclear emergency stop" for example) but only a safety-related system (as in numerous embedded automotive systems for example), the notion of safety function described in the ISO/CEI 61508 standard is not very easy to handle.

G u i d e l i n e s f o r t h e a p p l i c a t i o n o f p a r t s 2 a n d 3 O v e r v i e w o f t e c h n i q u e s a n d m e a s u r e s P A R T 7 P A R T 6 R i s k b a s e d a p p r o a c h e s t o t h e d e v e l o p m e n t o f t h e s a f e t y i n t e g r i t y r e q u i r e m e n t

P A R T 1 P A R T 1 I n s t a l l a t i o n a n d c o m m i s s i o n i n g a n d s a f e t y v a l i d a t i o n o f E / E / P E s a f e t y -r e l a t e d s y s t e m s

. 1 3 a n d . 1 4 P A R T 1 O p e r a t i o n a n d m a i n t e n a n c e , m o d i f i c a t i o n a n d r e t r o f i t , d e c o m m i s i o n i n g o r d i s p o s a l o f E / E / P E s a f e t y -r e l a t e d s y s t e m s

P A R T 1 7 . 1 5 t o 7 . 1 7 M a n a g e m e n t o f f u n c t i o n a l s a f e t y P A R T 1 D o c u m e n t a t i o n P A R T 1 D e f i n i t i o n s a n d a b b r e v i a t i o n s P A R T 4 F u n c t i o n a l s a f e t y a s s e s s m e n t P A R T 1

C l a u s e 6 C l a u s e 8

C l a u s e 5 a n d a n n e x A

O t h e r r e q u i r e m e n t s T e c h n i c a l r e q u i r e m e n t s

Figure 1 :Safety requirements

As it was designed to be a generic standard, the IEC 61508 standard has quickly led to several derivatives more adapted to specific areas. This has resulted in what we call the "ISO/IEC 61508 family" that is regularly enriched and consists today among others in:

• Using the ISO/IEC 15026 standard instead of the ISO/IEC 61508 standard brings the advantage to avoid the burden of the second standard as described in paragraph 2.2.

In the ISO/IEC 15026 standard, an integrity assurance authority is indeed in charge of assessing the compliance of the system with its integrity requirements.

Once the safety integrity level determination has been correctly done and assessed by the integrity assurance authority, each industrial may define the techniques that are the most appropriate to its context. The only requirements to fulfil is again to get the assessment of the integrity assurance authority on the set of techniques proposed to achieve the degree of confidence necessary for each integrity level.

Comparison between ISO 27005 and ISO 15028

The first important communality to highlight is that both standards are fundamentally based on a "risk management oriented" approach. This ISO 27005 summarizes its approach in the following figure: .

Figure 2 : ISO 27 005 process

The previous diagram show clearly the convergence announced between ISO 27005 and IEC 15026. That convergence enables the risk manager to operate as well in the security point of view during the analysis to prevent malicious attacks as in the safety point of view to prevent from unplanned system failure.

It is however important to notice that this parallelism between security and safety standards has been made feasible only provided that a common vocabulary is set up between the two areas. For example:

• « high level assessment » described in § 8.1 of ISO 27005 is comparable to « risk analysis during the specification phase », • « next iteration further in depth » also described in § 8.1 of ISO 27005 is associated to « risk analysis during the design phase », • the concepts of "primary assets" and "supporting assets " used by ISO 27005 are equivalent to the concepts of "functions" and "organs" used in system engineering, • etc.

From a process point of view; the ISO/IEC 15026 does not require support processes such as « communication » or « monitoring and review » in the ISO 27005 standard. However these processes are taken into account by the ISO/IEC 61508 family standards. Inversely some other useful support process such as "change management" should be taken into account into the ISO 27005 standard.

Benefits of the convergence

As new technologies become increasingly complex, the need to merge security and safety processes in a common analysis process is crucial. The convergence is mainly useful to reduce analysis time and cost for security and safety. To be efficient, only one engineer should work on both. He should have both expertises to achieve his task. Indeed, the analysis tasks for a system require being aware of all specification and conception data. This requirement takes a long time, especially in a complex system. This task done for safety is so not required for security.

An other benefit is the simplification of the project organization. The process is unique between safety and security. The interlocutor is also unique.

The third advantage is the proposition of recommendation coherent between the safety needed and the security needed. For example, in naval ship, a local must be always closed if there are some sensitive cryptographic algorithms processing inside. This is a main security requirement often proposed as recommendation. In the safety point of view, in certain condition, the door of the local will be demanded to be kept opened to permit the evacuation in case of fire. These two recommendations are antinomic but expected. Only the risk analysis even though in security and safety point of view will find the recommendation so needed.

Conclusion

This paper has provided guidelines to manage to create a unique process for safety and security. This process give immediate and long term benefits for companies. DCNS uses this approach without trouble for all project demanding safety and security analysis. In the future, we expected a more pronounced convergence by the emergence of a unique and global standard addressing security and safety.

Acknowledgement

We would like to thanks MATHIX Company for helping DCNS to build the adapted safety/security process.

And besides, the ISO/CEI 15026 standard describes its approach through the following figure: Another important communality is that the processes required by both standards are very similar and can be easily merged into a unique "generalized safety process" as it is explained in the following section.

Generalised safety process

In order to harmonize the safety and security processes at DCNS, a "generalized safety process" has been designed. The main phases of this process are:

• Definition and scheduling of safety activities

• Preliminary hazard analysis


A Pierre Gaufillet

B Sébastien Gabel

Avionic Software Development with TOPCASED SAM

Keywords: models, SAM, Topcased, avionics, requirements, verification

SAM, a graphical language dedicated to functional split up activities, has been introduced in several pilot projects at Airbus to support software specification. This article presents the needs that led to its development, the main components of its toolset and the conclusions after a few months of usage in an industrial context.

Airbus avionics development cycle

The development process of avionics equipment at Airbus follows a classical V cycle (see Figure 1). System engineers produce functional requirements documents that are analysed by avionic equipment teams. These requirements are then allocated to hardware or software subsets.

Let's focus on the phase of software specification in this process: the first operation of the software specifiers consists in defining hierarchically a functional architecture organizing the answer to the upstream requirements. Beyond this organization, the data and control flows between the functions need to be identified. Once this stage has been reasonably completed, the terminal functions of this functional split up are allocated to industrial subsets -these subsets are defined depending on various industrial constraints like teamwork, industrial partnerships, physical partition, re-use of existing components, segregation of different level of criticality, etc. Each subset is then exported to a specific team who will refine the functional split up until the required level of details. This refinement will be the basis of the subsequent technical design.

Software specification

To perform these specification stages, only a few abstractions are necessary:

Requirements

To ensure that the applications fulfil the needs of the customer, development choices have to be tracked step by step. Of course, those choices are more or less detailed depending on the considered stage of development, but they all cover one or more upstream needs, and will be covered by one or more lower level choices until the implementation stage. These customer needs and development choices are called requirements. They may be described informally -natural language, free-hand schemasor formally -abstract code, state machines, activities flow.

Functions

Fundamental building block of these specifications, functions identifies behavioral sets featuring inputs and outputs. Functions may be decomposed in smaller functions, to ensure that the complexity of the description is limited to the strict minimum for a given level of description. Terminal function's behavior is specified by requirements.

Flows

Flows are a side effect of the functional split up: they bridge the gap between the functions that have been defined, ensuring the communication of events and data between them. Flows require a special care, as they will lead more or less directly to define the API of the applications.

Modeling

SAM history

To improve maintainability and automatize as much operations as possible, we chose years ago to follow a MDE approach to support the specification stages.

It led us to derive a simple modeling language from the SART concepts called SAM -for Structured Analysis Model. SAM has been designed to cover precisely the concepts seen in section 2, and was initially supported by Sildex, a tool based on the SIGNAL language and developed by the company Geensys. As SAM gathers only a mere 50 concepts compared to hundreds in UML, it was a good candidate in Topcased 1 to develop a complete tool chain as required by our process. As most of Topcased tools, SAM ones have been themselves developed using MDE paradigm: the graphical editor for example is based on an ECORE meta-model and has been partially generated.

When Topcased 2 was published in 2008, SAM core tools were mature enough to be deployed on pilot projects. We therefore began to add typically industrial new features and to refine the existing components with the pilot project teams. This collaboration brought a lot of improvements and some brand new features like requirement management in SAM models.

SAM concepts

SAM defines a limited -but sufficient -number of concepts in order to facilitate learning and understanding the models produced. The current version, SAM 1.2, includes 40 concepts, and the version to come, SAM 1.3, will grow up to 48 concepts. Only SAM 1.2 will be covered here (SAM 1.3 extends the hierarchical approach to flows description).

Hierarchical approach

SAM, accordingly to the software specification needs described in section 2, defines a hierarchical architecture of functions. The software -or sometimes its environment -being designed is modeled as the root function. It is then successively decomposed into several sub-functions until the expected degree of detail is reached.

There are 2 kinds of function:

System: it represents a function that may be decomposed into smaller functions or not, with input and output interfaces (ports Cf. §3.2.2) connected via flows.

Automaton: closely related to Mealy state machines, Automata are a convenient mean to describe formally deterministic behaviors and therefore requirements that generate an output based on their current state and input. Of course, Automata are leaves of SAM models, and can own control, data and message input ports and control output ports. Depending on the destination of an Automaton (documentation, code / test plans / formal properties generation, model checking), data and message input ports may be forbidden. Flow: connect two ports of the same type and define communication means and synchronisation methods for systems and automata. This notion is oriented.

DataStorage: this component, once connected on a data flow, means that this flow is persistent: i.e. data are kept from one system's life phase to another.  A set of output ports that define precisely the events emitted when the transition is fired.

 A priority represented by a natural value. Priorities are required to select which transition is to be fired when several are possible.

Graphical Editor

Partially generated few years ago thanks to the Topcased editor generator, this graphical editor is nowadays maintained manually when modifications are required or when the SAM meta-model evolves. For this purpose, a model-to-model transformation using ATL has been developed and integrated into TOPCASED. And as history is prone to repetition, a complete process has been implemented to ensure the migration of SAM models from each meta-model version (1.1, 1.1.1, 1.2 and 1.3) to its successor. That is why today, we are still able to import a Sildex model into a SAM model conform to the latest SAM definition.

Requirements manager

In 2008, a new tool aiming to manage textual requirements in SAM environment has been introduced.

The goals were to establish links between textual requirements and model elements, and to describe how the current requirements are covering their upstream requirements.

Requirements concepts

Our approach is based on TRAMway. This component, developed in TOPCASED by Geensys, defines a meta-model that includes all the requirements concepts that may be useful in a modelling environment. TRAMway also provides a simple traceability solution working on a documents tree (specification, design, validation plan, test plan, etc.). An Open Office document parser is provided with this tool to import requirements, but they may also be directly injected in a XMI format.

But the TRAMway meta-model was not rich enough to fully describe the requirements used in avionics software specification documents. It has to be extended with new concepts such as requirement allocation; untraced, problematic and unaffected relationships requirements; and even requirement project configuration. With these extensions, a current requirement references two different elements: one SAM element and one upstream requirement.

TRAMway requirements importers are not yet powerful enough to process complex documentation formats. But hopefully, Reqtify is able to do it, and directly generate TRAMway models.

GUI

The requirement manager proposes several tools:  The upstream view: shows the upstream part imported in read-only. This tree hierarchy is structured in documents containing sections where upstream requirements are stored. A simple drag and drop operation, from one or a group of upstream requirements to a graphical SAM element, will create one or several current requirements. Upstream requirements appear with a bold italic font style as soon as they are covered at least once by a current requirement. For each container, it is possible to alter the order of requirements and free texts.

The document generator will later respects this order in each container section.

OCL tools

Another need is to verify the consistency of models at any time during the modeling phase. The OCL tools offer a transparent integration with all TOPCASED modelers. Based on MDT OCL, this component allows writing OCL rules, evaluating them on models and visualizing the results in a dedicated form.

About 80 OCL rules have been defined to verify the static semantics of SAM models. They provide the end user with information and relevant to help him fixing his models. These OCL rules have been integrated into SAM plug-in and are available when users edit their model in the editor. Users must nevertheless launch manually the verification thanks to the corresponding tool bar action: this is not a live validation but a static one.

The verification results of these rules are notified into the Eclipse problem view. Corresponding decorators are displayed on graphical elements to help with identifying erroneous or incorrect elements. A double click on a problem sets the selection to the corresponding element in a diagram or in the Outline view.

Team work support

In real life, models soon become so big that several designers have to work concurrently on them. Topcased includes a feature supporting such approach. Once the main model has been initiated, it is possible to lock and export sub-tree of it. Each designer then works independently on its parts, without even needing to access the main model.

Once a designer finished its set of modifications, Topcased re-import them in the main model and unlock the corresponding sub-tree. If the interfaces between the main model and the sub-tree evolved inconsistently, they are also reconciled semiautomatically.

Airbus customisations

Of course, even if they have been designed with Airbus needs in mind, local customisations are often needed. To shorten the Time to Desktop of these customisations, several features have been used:

 Javascript/Python scripting engines: by providing a script-style API, these engines allow to implement model to model transformations (initialisation of the subset definition from the split up model for example), to build editing macros for specific actions. The scripts are easy to deploy and to launch from the Eclipse GUI.

 Acceleo model to text generators engine: Acceleo has been used to build quickly data extractors (flow dictionary preview, upstream requirements covering status, etc.).

 Gendoc Document generator: with the now classical template approach of Gendoc, it is possible to adapt the output format to the user's needs with no or very few Java developments.

Even with these frameworks, customisation remains a time consuming operation: dozens of scripts and templates have been developed to tune the modelling environment for specific needs.

Deployment

Functional aspect is not the only important one for a tool chain: its deployment may also be more or complex, depending on the need, the platforms, etc. At Airbus, Topcased components are not deployed in the standard bundle provided on the web site. To improve stability and functionalities, they are packaged in a specific feature that excludes unused and most experimental features -but a few ones absolutely. This bundle also includes a few specific plug-ins -generators, scripts, etc. -and some other eclipse features useful to our developments -the C and Java Development Toolkit, several VCS clients, scripts editors, etc.

This installation is provided for Solaris 8 & 10, Linux and Windows platforms. Due to the organization of our department, several deployments are then produced:

 A centralized deployment: eclipse is installed along with all the required features on a network drive. This is the preferred installation for internal users using Unix stations. Of course, a decent network bandwidth and latency is required to work this way: a 100Mb/s ethernet LAN is required.

 A full-featured eclipse archived in a zip file.

To install it, it is only needed to unpack it on the local disk of the station. This is the preferred installation for external users (industrial partners) and windows platform.

Note that in an extended enterprise context, the fact that this bundle is available under the Eclipse Public

License, an open source license, is a real advantage. There is therefore no need for specific licensing/lending/renting contracts.

On the performances side, our platforms are not equal faced to eclipse and Topcased. Most people would say that Windows would be the fastest one, due to the efforts of optimisation that have been done on the Java virtual machine and because eclipse is mainly developed on it, but it is not. It seems that our internal configuration slows down eclipse a lot: in some situations, eclipse can take several minutes to get launched! Moreover, some problems of stability have not been resolved, leading sometimes to crash completely the system. Solaris and Linux appear far more robust. Solaris has decent performances but it is Linux that offer the best performances (probably due to the more efficient underlying hardware, a more optimised JVM and a better X11 server).

Conclusion

After a few months of work with this toolset in real industrial conditions, we can conclude that:

 Topcased SAM now offers a functional tool chain, covering most user needs for software specification for models up to (at least) a few thousands elements.

 The model editor is seen as quite user friendly, even if for some activities (model refactoring, HTML edition, etc.) it still can be improved.

 The required support tools complete it efficiently: requirements editors, static semantics verification engine, text / model / documents generators & scripting engines.

 Test plans and soon formal properties generations improve greatly the productivity when the behavior can be described as Automata.

 The fact that the tools help is integrated is also seen as a big advantage.

 The lock/unlock approach for teamwork is still not robust enough and may be also functionally improved (CDO for example may be used to allow a finer and smoother locking grain).

 There are still some performances issues around large models and with our Windows platform. These locks are currently investigated and we hope to overcome them soon (the latest Topcased releases already include some related improvements).

In brief, the SAM toolset can now be considered as a complete and customisable solution for small & medium size projects. Its remaining flaws nevertheless have to be fixed before to deploy it to a larger scale.

[1] Topcased: http://www.topcased.org

[2] Eclipse Modeling Project: http://www.eclipse.org/projects/project_summary.php? projectid=modeling

Glossary

Figure

  Figure 1 -V model

Figure 2 :

 2 Figure 2 : System and Automaton with flows 3.2.2 System children SAM also includes the following detailed features that may be contained by a System: Port: define input and output interfaces of the different components. Ports can be typed as data (a typed value), control (an event) or message (both typed value and event) to propagate a piece of information.

Figure 3 :

 3 Figure 3 : DataStorage figure Broadcast, Merge and Split : these components allow to multiply the number of flow producers or consumers.

Figure 4 :

 4 Figure 4 : Broadcast, Merge and Split figures Composition and Decomposition : used to define structured data. The first one allows gathering several data flows, while the second extracts data flows from a composite flow.

Figure 5 :

 5 Figure 5 : Composition and Decomposition 3.2.3 Automaton children Automata are build with 2 main families of elements:

Figure 6 :

 6 Figure 6 : Automaton diagram

Figure 7 :

 7 Figure 7 : System diagram in SAM editor As in the other Topcased graphical editors, we find the following layout: a tools palette is located on the left of the editor area -its content is updated in accordance with the kind of diagram displayed. The user may arrange views around the main edit area according to its needs and work habits. The Eclipse menu bar gives access to basic graphical features such as show/hide grid, elements alignment, snap to geometry, zoom, etc. but also t o navigation (go to next, previous, parent diagram) and model verification (EMF and OCL validations). The SAM properties or the graphical properties of any model elements can be edited thanks to traditional views offered by Eclipse (as the Outline or Property views) or specifically by Topcased. The Documentation view for example allows manipulating complex HTML bodies such as comments or requirement description. It also enables to associate URL links or external documents.

Figure 8 :

 8 Figure 8 : TOPCASED Docmentation View 4.3 Import Sildex legacy models Of course, almost no tool is introduced into industrial process without taking care of legacy data. SAM tools are not an exception in that domain: porting the existing models from Sildex to SAM was a real concern.



  Generate a requirement model from a document (odt, ods, etc.) or from a Reqtify export,  Attach the requirement file to a SAM model and creates requirement links between current requirements and graphical model elements, between current requirements and upstream requirements,  Export specification documents including schemas and requirements.

Figure 9 :

 9 Figure 9 : Upstream Requirement view  The current view: presents a set of current requirements and free texts in a tree reflecting the SAM model itself. Requirements are organized accordingly to their SAM model container.For each container, it is possible to alter the order of requirements and free texts.The document generator will later respects this order in each container section.

Figure 10 :

 10 Figure 10 : Current Requirement view  Preview: provides a real document generator limited to raw text. This view allows the user to

Figure 11 :

 11 Figure 11 : Preview, a step toward the final document generation It became clear quite soon that the requirement manager was not at all specific to SAM. It led us to study its generalization as a new component. Recent experimentations done with UML/SysML proved the interest of this solution. The developments done for SAM are gradually adapted and migrated to this generic requirement manager.

CDO:

  EMF project providing distributed shared model edition capabilities DSL: Domain Specific Language EMF: Eclipse Modeling Framework EMP: Eclipse Modeling Project HTML: HyperText Markup Language M2M: Model-To-Model M2T: Model-To-text MDE: Model Driven Engineering OCL: Object Constraint Language SAM: Structured Analysis Model SART: Structured Analysis for Real Time Topcased: Toolkit in OPen source for Critical Applications and SystEm Development UML: Unified Modeling Language VF: Validation Framework


Dr Fridtjof Siebert
email: siebert@aicas.com

Multicore Systems -Challenges for the Real-Time Software Developer

Keywords: C.3 [Computer Systems Organization]: SPECIAL-PURPOSE AND APPLICATION-BASED SYSTEMS-Real-time and embedded systems, D.3.3 [Software]: PROGRAM-MING LANGUAGES-Language Constructs and Features, D.4.7 [Software]: OPERATING SYSTEMS-Organization and Design: Real-time systems and embedded systems algorithms, languages, performance, reliability multicore, parallel, concurrent, real-time, Java, memory

Multicore systems have become the norm for desktop computer systems. The percentage of multicore systems in the embedded domain is still marginal, but growing at an incredible pace such that multicore will become the norm in the embedded area as well. However, embedded systems have additional requirements with respect to safety, reliability, and real-time behaviour. The use of parallel multicore systems introduces new challenges to the embedded systems developer who has to fulfil these requirements when developing new software or porting existing code to multicore systems.

This paper gives an overview over typical problems that arise with the use of multicore systems. Unfortunately, a multicore system in many cases does not behave the same as a single core system with multithreading. These differences may result in severe program errors. A good understanding of the sources of these errors is required.

It will be explained how problems on multicore systems can be avoided. Mechanisms present in different programming languages such as C/C++ and Java will be presented. An important role is played by the memory model provided by the language implementation and how this may manifest in false program behaviour. The memory model permits different compiler and CPU optimisation on atomic and non-atomic operations, and allow different semantics of the volatile modifier.

The use of multicore systems may have very surprising negative effects on performance. The paper describes these effects and how they can be avoided by avoiding synchronization or using lock-free algorithms. The implications that come from the real-time requirements on these techniques will be taken into special account.

Introduction

The emergence of multicore computer architectures will have a profound effect on the software development process and the implementation of programming languages. With multicore systems, parallel systems become the norm even for low-end computers such as embedded controllers.

Typical problems

The typical problem on multicore systems arise from missing synchronization primitives. The basic synchronization primitives available are locks (mutexes, semaphores) and compiler hints such as the volatile flag.

Synchronization

As a very simple initial example (in C or Java), I take the code from figure 1 which declares a counter variable and a routine to increment it.

Assume that the routine increment() is used concurrently by different threads. Incrementing an int using the post-fix ++ operation is not atomic, so we have a race condition in this code, concurrently executed calls to increment() may result in some increments getting 1: int counter; 2: 3: void increment() 4: { 5: counter++; 6: } Figure 1. Non-synchronized code to increment a counter variable missed. However, it may well be that this code never showed any problems on a single core system.

Assume that increment() is called about 100 times every second after one of several possible events occurred. On a single-CPU system, the code may work fine all of the time: If all events are handled by threads of the same priority the code will not be preempted and the race condition here is merely theoretical.

On a two CPU system, the event handlers may execute concurrently. Assuming that increment() requires 100 cycles and we run at 500MHz, the likelihood of a conflict is about 10% each second. If increment() was called 1000 times per second, the likelihood of failure within one second is 99.99%! Fixing this problem is easy, add synchronization as in figure 2 (in Java). The overhead required for the synchronization is relatively low, and all the problems described above are fixed. In Java, it has therefore become practice to add synchronized keywords generously whenever multiple threads may simultaneously access modifiable data.

Theoretical Limits

The performance to be gained on multicore systems by parallel execution has an important theoretical bound defined by Amdahl's law [START_REF] Hill | Amdahl's law in the multicore era[END_REF]. It is plain and simple, you gain only on the sections of the application that can be parallelized, sequential code does not profit from parallel CPUs. Unfortunately, if the number of CPUs increases, the remaining sequential code becomes more and more dominant, such that, e.g., having only 25% of sequential code will limit the performance gain on a multicore system to a factor of four, no matter how many CPUs are available.

However, this paper does not address Amdahl's law, but addresses issues of inter-thread communication that result in a situation that is much worse in practice: If not designed well and correctly, thread interactions result in failures or severe performance bottlenecks that are much worse than what Amdahl's law would predict.

Memory Model

The basis for software development on a multicore system (and even on a multi-threaded system running on a single core) is the memory model defined in the programming language. The memory model defines the semantics that parallel accesses to memory location have, and the diversions from straight sequential semantics that the compiler and the CPU implementation is allowed to make. The memory model is therefore fundamental for the development of applications with a well defined behaviour.

Java is very advanced in this respect as the Java community early on discovered the importance of the memory model and the flaws of the original specification [START_REF] Pugh | The java memory model is fatally flawed[END_REF], to come up with a robust memory model [START_REF] Manson | The java memory model[END_REF] the developer can rely on. The C++ programming languages is catching up by also clarifying its memory model [START_REF] Boehm | Foundations of the c++ concurrency memory model[END_REF], but the C++ community's approach is more relaxed requiring more care by the developer. The memory model of the C programming language is undefined for multi-threaded applications, which allows the largest number of compiler optimisations, but it makes this language unsuitable for the development of multi-threaded code. In particular with the advent of more and more multicore systems, the undefined semantics in C render this language a major risk for the development of safety-critical applications.

The main differences between these memory models will be explained below in this paper.

Correctness on Multicore Systems

Code that was developed for single CPUs and that was verified and tested extensively on single CPU systems may be incorrect on a multicore system. Even though a single CPU system uses multi-threading that gives the illusion to the software developer that several CPUs are present, the run-time semantics on multicore systems are significantly different and allow for interleaving of code execution that is impossible on a single core and that can cause fatal failure when moving single-core code to a multicore system.

Figure 3 shows a simple code sequence that runs correctly on a single CPU system, but that may fail on a multicore system. This example uses two real-time threads that perform a high-and a low-priority task regularly. This code was developed to run on a real-time A high-and a low-priority task that interact correctly on a single-core, but that can cause a crash on a multicore since the high priority task may be preempted by the low priority task system with preemptible fixed-priority scheduling, i.e., the low priority task may always be preempted by the high priority task, while the high priority task will always complete without being preempted by the low priority task. These two tasks communicate via a shared variable index that identifies a data slot to be read by the high priority task. A negative value for index indicates that no data should be read. The high priority task reads index twice, first to check whether it is non-negative, and, in case this test was successful. to write the read data into the slot referred to by index. This works perfectly on a single CPU system since the low priority task cannot modify index once the high priority task has started execution.

However, on a multicore system, these two tasks may actually run in parallel on different CPUs resulting in the execution interleaving shown in Figure 4. The low priority task may modify the value of index at any point during the execution of the high priority task resulting in using a negative array index.

The problem with this kind of code is that even very extensive testing might not be sufficient to discover these kinds of problems. An in-depth review of single-CPU code is required to ensure that it runs properly on multicore systems.

The situation becomes worse when the original code was already poorly designed and contains bugs. Imagine the two tasks from this example run at the same priority. The application contains a race conditions that may result in failures during run-time on a single core systems. However, these failures are very unlikely since they may only occur in case of a thread switch right after the first time index was read. On a multicore system, such a thread switch is not required, the two tasks will just naturally be assigned to different CPUs by the OS such that many more possible interleavings of memory accesses will occur at run time. This means that race conditions that may exists in multi-threaded software, but that never manifested in run-time failure on a single core systems may become orders of magnitude more likely to result in application failure on a multicore.

Performance on Multicore Systems

When moving a multi-threaded software system from a single core to a multicore platform, one would hope to see an increase in performance due to the possibility to run several threads in parallel on different CPUs, compared to being limited to one thread at each point in time on a single CPU system.

Unfortunately, instead of a performance increase, the result of moving to multicore is a severe performance decrease in many cases. The reason for this lies in different thread communication patterns that may occur on parallel systems.

Figure 5 illustrates a piece of real-time code that performs well on a single-CPU system. A low priority task regularly checks a shared variable index that is occasionally updated by a high priority task. To avoid race conditions, all accesses to the shared variable are synchronized using a Java monitor.

When running this code on a single CPU system, the high priority task may preempt the low priority task at any time. If the high priority task is unlucky, this preemption will occur while the low priority task is within its synchronized block. Then, the high priority task will have to wait for the low priority task to leave that section the first time the high priority task enters the same lock. Standard priority inheritance techniques ensure that this happens in bounded time. On any subsequent iterations of the loop in the high priority task, no synchronization is required: The low priority task cannot

. Two communicating threads that perform well on a single CPU, but that may cause a severe slowdown in the high priority thread on a multicore system run and re-acquire the lock such that no further blocking of the high priority task will occur. On a single core, there is therefore very little interthread communication in this application. The behaviour is shown in Figure 6.

When running on a multi core, however, the high priority task can see an extreme slowdown as shown in Figure 7. In this case, the low priority thread can run in parallel to the high priority thread, such that it can re-acquire the lock again and again, forcing the high priority thread to block repeatedly.

The Memory Models in Java, C++ and C

To understand well what kind of synchronization mechanism are required in the code, the developer of parallel software first needs to understand the memory model of the underlying programming language that is implemented by the compiler and run-time system in use. The memory model must allow for sufficient compiler and hardware optimisations, while it also must give the developer a good understanding of how the execution environment may execute the code. Java was the first mainstream programming language for which a reliable memory model was defined [START_REF] Manson | The java memory model[END_REF][START_REF] Ševčík | On validity of program transformations in the java memory model[END_REF][START_REF] Jaroslav | The java memory model (tutorial)[END_REF]. Since this language has built-in support for threads and synchronization mechanisms, a clear specification of the behaviour is required. The C++ community is currently working on their own memory model [START_REF] Boehm | Foundations of the c++ concurrency memory model[END_REF], based on the Java approach, but with important relaxations making execution of C++ software less predictable.

For the C language, the language specification does not define the memory model at all. Consequently, only single-threaded applications can be written safely in C. For multi-threaded applications, the developer must understand the particular C compiler in use well enough to know what code this compiler will generate and possibly include processor-specific memory fences manually into the code.

The memory model is a contract between the hardware, compiler and the developers. It describes the legal behaviours of multi-threaded code with respect to shared memory. This is the basis to reason about multithreaded programs, to give security guarantees and to allow optimisations in the compiler.

The Java memory model

An important part of the Java memory model is the definition of so-called ordering operations. These ordering operations are entering or exiting synchronized blocks and accesses to volatile fields. The Java memory model permits certain reordering of memory accesses, but it is very strict on the reordering over ordering operations. Finally, final fields require specific handling in the Java memory model

The following subsection will describe the aspects of the memory model in more detail.

Reordering

The Java memory model allows compilers to reorder independent statements. It in particular allows optimisations that are

• trace preserving, i.e. result in the same memory access patterns, e.g.

if (r == 1) x = r; else x = 1;
can be replaced by x = 1;

• removal of irrelevant reads • memory access reordering, e.g., r1 = x; r2 = y; <=> r2 = y; r1 = x; x = r1; y = r2; <=> y = r2; x = r1; r1 = x; y = r2; <=> y = r2; r1 = x;

• removal of redundant read after write, e.g.,

x = r1; r2 = x;
can be replaced by x = r1; r2 = r1;

• removal of redundant reads, e.g., r1 = x; r2 = x; can be replaced by r1 = x; r2 = r2;

• removal of redundant write before write, e.g., x = r1; x = r2; can be replaced by

x = r2;
Not allowed are the following modifications

• additions of irrelevant reads • removal of redundant writes after read, e.g.,

r1 = x; x = r1;
can not be replaced by r1 = x;

• moving memory accesses into a synchronized section, e.g.,

volatile fields and synchronization

Entering a synchronized block or reading a volatile field ensures that all reads of shared memory are completed before the synchronization operation is performed. Symmetrically, leaving a synchronized block or writing a volatile field ensures that all writes have been performed before the synchronization operation is performed.

The memory model guarantees that certain memory accesses will not be moved over an ordering operation by the compiler or the underlying hardware. In particular, no memory reads from shared memory that occur before entering a synchronized block or reading a volatile field will be performed after this ordering operation. Symmetrically, all memory writes to shared memory that occur before exiting a synchronized block or writing a volatile field will become visible to other threads before executing the ordering operation.

final fields

A special treatment of final fields is required by the Java memory model. If an object's constructor initialises a final field before the object reference is handed over to other threads, it is guaranteed that this initialisation becomes visible to other threads before they can access this field, even in the absence of any synchronization mechanisms.

The C++ memory model

The memory model used for C++ is more generous when it comes to permitted optimisations by the compiler. This flexibility for the compiler comes at the cost of loss of predictability: Unlike Java, a C++ application with data races has an undefined behaviour. It therefore lies in the responsibility of the developer to avoid all race-conditions or to have an in-depth knowledge about the compiler.

Lock-free algorithms -the solution?

Lock-free algorithms avoid the use of high-level synchronization mechanisms such as locks and use more primitive operations such as compare-and-swap (CAS) instead. A CAS is an atomic operation with the semantics shown in Figure 8. The use of lock-free algorithms may help to overcome the performance problems that explicit synchronization introduces. Coming back to the simple example from figure 1 that increments a counter: This code can be made thread safe through usage of lock free operations such as compare-and-swap (CAS) as shown in figure 9. However, this code based on CAS is difficult to understand, even for this very simple case. More complex algorithms using such lock-free mechanisms quickly become extremely difficult to develop and practically impossible to maintain. It is therefore a good idea to restrict the use of lock-free algorithms to individually developed and thoroughly tested libraries. In the case of Java, the package java.util.concurrent provides such library code. Figure 10 illustrates how a lock free counter can be implemented using class AtomicInteger from this package. counter.incrementAndGet(); 6: } Figure 10. Use of lock-free library code to increment a counter variable When developing real-time code, it is required that we can give reasonable worst-case execution time bounds for all time-critical code. However, the use of a CAS instruction typically requires a possibly infinite number of retries. E.g., for the CAS that is executed in the loop shown in figure 9 it is difficult to find an upper bound on the number of iterations of this loop. Therefore, this code cannot be used in an environment that requires strict timing bounds.

The following sub-sections explain under which conditions CAS-based lock-free code can be used even for time-critical tasks.

Compare-And-Swap for One-Way State

Changes An application may make use of state variables whose value can change only in one specific direction, i.e., if the current state is A, the state variable can only be changed to B. A phase change from A to B may be attempted by several CPUs in parallel using compareand-swap. Only one CPU will succeed with this operation. However, the failed CPUs do not need to retry the CAS since the operation failed because some other CPU made exactly the state change that the failed CPUs attempted to make. In contrast, a CAS in the general case can fail and require one or several retries in case another CPU in parallel writes the same word. One-way state changes do not require a retry even when performed in parallel.

Care is needed to ensure that a CAS on a state change does not fail due to a cycle of states (the ABA problem): e.g., imagine CPU1 attempts to change the state from A to B and this unlucky CPU is so slow (it may be pre-empted by the OS to perform some completely different task) that another CPU2 will perform the state change to B, will finish phases B, C, D, etc. and finally put the system back into phase A. If now CPU1 will execute its compare-and-swap, it will perform the state change to B even if the newly started phase A is not complete yet. To solve this, for any such cycles in state changes, it has to be ensured that at some point during the cycle, no CPU is in the middle of attempting a state change.

In general, a CAS for a one-way state change can be used in a real-time system straightforwardly, a worstcase execution time can be found since no retries are needed.

Compare-And-Swap with Retry

Less useful for real-time systems are CAS-loops that retry the CAS operation in case it failed. This approach is sufficient for non-real-time systems that are optimised for average throughput, but not being able to limit the number of CAS-retries is not acceptable in a real-time system.

The number of CAS-loop iterations can, however, be limited to n if the number of CPUs is limited by n and the number of CPU cycles spent in between two successive executions of such a loop is at least n-1 times larger than the time required for one CASloop iteration. The reason for this is that if a CAS failed on one CPU, a competing CAS on another CPU must have been successful. Hence, this other CPU will then perform work outside the CAS-loop. The same will happen for each following iteration with a failing CAS. After n-1 failed CAS-loops, all other CPUs will be in the CAS-free code section and the nth CAS is guaranteed to succeed1 .

Conclusions

The upcoming multicore systems have a deep impact on the software development for real-time and embedded systems. It is not possible to port existing singleprocessor code to a multicore system without thorough analysis of the code. In particular real-time software may show failure or severe performance degradation as a result of the move to multicore systems.

A thorough understanding of the memory model provided by the programming language is required for the development of multi-threaded software that should benefit from multicores. Java currently provides the most reliable memory model, while the C++ community is currently working on a less strict model. C does not give any guarantees on the memory model and multi-threaded execution.

The use of lock-free algorithms may solve some important performance issues. However, the techniques are extremely complex and require skilled personnel and careful engineering to an extend that lock free algorithms will likely remain the realm of a few highly specialised developers.

An application architecture that avoids most of these problems while benefiting from multicore systems would try to be parallel at the large scale: Large independent code sections that may run in parallel will not suffer from problems related to synchronization or inter-thread communication. The goal has to be to design applications this way.

Figure 2 .

 2 Figure 2. Synchronized code to increment a counter variable

Figure 3 .

 3 Figure3. A high-and a low-priority task that interact correctly on a single-core, but that can cause a crash on a multicore since the high priority task may be preempted by the low priority task

  [index] = readData();

Figure 4 .

 4 Figure 4. Possible interleaving of example from Figure 3 that results using the illegal array index -10000.

Figure 6 .

 6 Figure 6. Locking in the example from Figure 5 between a low-priority and a high-priority thread causes little thread interaction on a single core.

Figure 7 .

 7 Figure 7. Locking in the example from Figure 5 between a low-priority and a high-priority thread causes extreme slowdown for the high priority thread on a multicore.

Figure 8 .

 8 Figure 8. Semantics of CAS as used in this paper

Figure 9 .

 9 Figure 9. Use of Compare-And-Swap to increment a counter variable

On real systems, determining the precise time spent in the loop is more complex, including interrupts or cache effects. Nevertheless, using a large enough code sequence between two successive CAS-In consequence, a CAS with a retry-loop is only usable in a real-time system if the CAS-free code section after the CAS-loop can be made large enough. Ideally, the length of the CAS-free part should be configurable by a run-time constant to permit scaling for arbitrary numbers of CPUs.

Acknowledgement

This work was partially funded by the European Commission's 7th framework program's JEOPARD project, #216682.