1、Analysis of Safety-Critical & Mission-Critical Systems Using ASIS,An Interface to the Ada 95 Compilation Environment,Mr. Currie Colket Chair, ACM/SIGAda/ASIS Working Group (ASISWG) Chair, ISO/IEC JTC1/SC22 WG9 ASIS Rapporteur Group (ASISRG) Phone: (703) 883-7381; Email: colketmitre.org, colketacm.or
2、g Dr. Bill Thomas Vice Chair, ASISWG for Publicity/Meetings Phone: (703) 883-6159; Email: bthomasmitre.org 4 May 1999 STC99 Electronic Copy on ASIS Home Page = http:/www.acm.org/sigada/WG/asiswg,Overview,Why Code Analysis for Safety/Mission-Critical SystemsWhat is ASIS? - Syntactic & Semantic Querie
3、s- Examples of Tools Built on ASISASIS ArchitectureTemplate for ASIS AnalysisExamples of Safety/Mission-Critical Analysis of CodeASIS is now ISO StandardSummary,An Interface to the Ada 95 Compilation Environment,Why Code Analysis for Mission-Critical Systems,Safety and security verification Quality
4、assessment metrics Test-case generation and coverage analysis Coding style and standards complianceTiming and sizing estimation Dependency trees and impact analysisData flow analysis and usage metrics Invocation (call) trees and cross-reference Usage counts of language constructs Code browsing and n
5、avigation Documentation generation Reverse engineering and re-engineering Language translation and code restructuring,Addressing these concerns results in higher quality systems,Safety/Quality Concerns,Performance Concerns,Engineering Concerns,Why Code Analysis for Safety-Critical Systems,Four Appro
6、aches required by standards to support the verification of software:TraceabilityReviewsAnalysisTesting,International Generic Safety Application Standard: IEC-61508 - (Part 3 concerns software)Sector specific guidance and standards:Airborne civil avionics DO-178BNuclear power plants IEC 880Medical Sy
7、stems IEC 601-4Pharmaceutical GAMPNational/regional guidance and standardsUK Defence DS 00-55European rail EN 50128European security ITSECUS Nuclear NRCUK Automotive MISRAUS medical FDAUS Space NASAGuidance for the use of the Ada Programming Language in High Integrity Systems Draft ISO/IEC TR 15942,
8、Analysis for Verification of Software,Analysis methods, required in different combinations by various standards:,Control Flow Data Flow Information Flow Formal Code Verification Range CheckingSymbolic Execution Stack Usage Timing Analysis Other Memory Usage Object Code Analysis,ASIS directly support
9、s these analysis methods,ASIS can indirectly support some of remaining analysis methods,What is ASIS?,Ada Source Code,Compile,Link,Provides Syntactic and Semantic Information from Ada Environment using a standard interface,Syntactic Information,Ada syntax is summarized in Ada 95 RM, Annex P as varia
10、nt of Backus-Naur Form,For example: object_declaration := defining_identifier_list : aliased constant subtype_indication := expression; | .For the Ada object declaration = A,B: Latitude := 0.0;Syntactic Element Tree Representation =,ASIS can extract desired syntactic information for every syntactic
11、category Of the 367 ASIS Queries, most support syntactic tree analysis,Semantic Information,These mechanisms allow ASIS to traverse the syntactic tree like Hypertext allows one to traverse a document,Type,Latitude,+90.0,Range,Defining Identifier,Static Simple Expressions,-90.0,Full Type Declaration,
12、Real Range Specification,Type Definition Real Type Definition Floating Point Definition,Ada semantics are provided via mechanisms such as Corresponding_:Corresponding_Type_Declaration, Corresponding_Name_Definition, Corresponding_Called_Function, Corresponding_Called_Entity, Corresponding_Type, Corr
13、esponding_Body, Corresponding_Entry, etc.,Digits,8,Static Expression,Corresponding_Name_Declaration,A := A + B;,Corresponding_ Name_Declaration,Corresponding_Expression_Type,Operations on Elements,Element,Enclosing Element,Element. A common abstraction used by ASIS to denote the syntax components (b
14、oth explicit and implicit) of ASIS compilation units.,Enclosing Compilation Unit,Related Elements,Kind,Component Elements,Text Span Text Image,ASIS Element Queries,Examples of Tools Built on ASIS,Ada Environment,Code Restructuring Tools Code Browsing and Navigation Tools Coding Style and Standards C
15、ompliance Tools Cross Reference Tools Data Flow Analysis Tools Dependency Tree Analysis Tools Design Tools Document Generation Tools Invocation (Call) Tree Analysis Tools Language-sensitive Editing and Prettyprinting Tools Language Translation Tools Quality Assessment Tools Reverse Engineering Tools
16、 Re-Engineering Tools Safety & Security Compliance Tools Static Correctness Verifiers Tasking Analysis Tools Test-case Generation & Coverage Analysis Tools Usage, Quality, & Complexity Metrics Tools,ASIS Interface,Tools portable to Ada environments supporting ASIS Interface,ASIS Lets Client Tools “S
17、nap On“ to Compilation Systems,etc.,Ada Program Library,Lockheed-Martin Tools,Ada Program Library,Boeing, MITRE Tools,Ada Program Library,Magnavox, MARK V Tools,Ada Program Library,Little Tree, SofTools Tools,Ada Environment,CCI GmbH, Sema Group Tools,Rational Ada Environment,GNAT Ada Environment,DD
18、C-I Ada Environment,Aonix Ada Environment,etc.,ASIS Usage,Compiler Implementers:ACTAonixConcurrent DDC-I Green HillsIntermetricsOC SystemsRational(very soon),Tool Vendors:AonixCCI GmbHDRC GRCLittle Tree ConsultingMark VORA CorpRationalSimulogSofToolsSwiss FederalInstitute of Tech,End Users:Air Force
19、BoeingFAAIBMLockheed-MartinLogiconLoral MagnavoxMITRENavy Sema GroupUnisys WPL Labs+HRG,* Usage not known, but voted approvalfor ASIS CD Final on ISO/IEC JTC1/SC22 Ballot,Countries:AustraliaBelgium *CanadaChinaCzech Republic *DenmarkEgypt *Finland *FranceGermany Ireland *JapanNetherlands *Norway *Ru
20、ssian FederationSwedenSwitzerlandUkraine *United KingdomUnited States,Ada95,Ada95,Ada95,Ada95,Ada95,Ada95,Ada95,ASIS Abstractions - Package ASIS,Ada Semantic Interface Specification (ASIS),Package Asis provides:Common types: ASIS_Integer, ASIS_Natural, ASIS_Positive,List_Index,Context, Element, Elem
21、ent_List, Element Subtypes,Element Kinds (collection of enumeration types),Compilation_Units, Compilation_Unit_List, Unit Kinds (collection of enumeration types), Traverse_Control, and Program_Text (subtype of Wide_String)Queries via 20 visible child packagesAda Exceptions for errors with Status & D
22、iagnostic information,Asis and child packages encapsulate vendor dependencies Designed to be portable for all implementations,ASIS Context,Context can be all compilation units in the active partition, a subset, or any set to which analysis is desired,ASIS Package Architecture,ASIS Abstractions - Ada
23、_Environments,Ada Semantic Interface Specification (ASIS),ASIS.Ada_Environments,Associate,Dissociate,Has_Associations,Open,Close,Is_Equal,Exists,Is_Open,Name,Default_Name,Parameters,Default_Parameter,Environment Model:Associates name and parametersOpen, Query, and CloseProvides analysis free of vend
24、or details and assumptions,Is_Identical,ASIS Context identifies an Ada Environment as defined by ISO/IEC 8652:1995 Ada 95 which allows implementations to define methods to enter Compilation Units into the environment,.,ASIS Abstractions - Compilation Units,Ada Semantic Interface Specification (ASIS)
25、,ASIS. Compilation_Units,Unit_Origin,Corresponding_Body,Corresponding_Children,Is_Equal,Attribute_Values,Has_Attribute,Exists,Can_Be_Main_Program,Subunits,“Times”,“Relations”,Compilation_Units,Unit_Kind,.,Provides external “Black Box” viewAttributes: Relationships: Compilation Unit Model Fetch by na
26、me Query of attributes & relationships Gateway to internal view using Elements,Date compiled, Text File, Compilation Options, Optimizations, Can Be a Main Program,Ancestors, Descendants, Supporters, Dependents, Family, Needed_Units,ASIS Abstractions - Elements,Ada Semantic Interface Specification (A
27、SIS),Asis.Elements . Asis.Clauses . Asis.Declarations . Asis.Definitions . Asis.Expressions . Asis.Statements . Asis.Exceptions . Asis.Iterator ,.,Provides internal “White Box” viewLogical handle to Ada elements: Element Model Element kinds Syntactical queries to classify and decompose syntactic ele
28、ments Semantic queries Elements know their enclosing Compilation Unit & Context,Declarations, Statements, Expressions, Type Definitions, With Clauses .,Element. A common abstraction used by ASIS to denote the syntax components (both explicit and implicit) of ASIS compilation units.,ASIS Abstractions
29、 - Implementation,Ada Semantic Interface Specification (ASIS),ASIS. Implementation,Is_Initialized,Is_Finalized,Status,Set_Status,Diagnosis,“Permissions”,.,Initialize,Finalize,Using ASIS:Asis.Implementation.Initialize; - To setup environment . - Determine ASIS implementation permissionsP := Asis.Impl
30、ementation.Permissions.Is_Line_Number_Supported; . Asis.Ada_Environments.Associate (.); - To name Ada context Asis.Ada_Environments.Open (.); - To gain (library) access .- Use various ASIS interfaces . Asis.Ada_Environments.Close (.); - To close (library) accessAsis.Ada_Environments.Disassociate (.)
31、; - To release contextAsis.Implementation.Finalize; - To release all resources,Analysis Characteristics of Mission-Critical Systems,Typical Analysis Characteristics: Large-Scale Software Systems Analyses performed throughout the product lifecycle Often unique, application or domain analyses Inconsis
32、tent/Incomplete Documentation Wide variety of compilation platforms Development and analysis platforms often are different,We need the ability to develop, enhance and maintain custom software analysis applications,We cannot depend on commercial products to support these requirements,ASIS provides st
33、rong support for the development of such new analyses,Sample Asis-based Application for Code Analysis,Examples of Code Analysis:1. Identification of Declarations for Information Flow Analysis2. Call Tree for Control Flow Analysis3. Restrictions Checker for Formal Code Verification- Reports the viola
34、tion and the line number of violation,But first an application template for ASIS-based Analysis- Useful for most ASIS-based Analysis- Examines all compilation units in an Ada Environment,with Asis; with Asis.Implementation; with Asis.Ada_Environments; - other ASIS packages, as required with Asis.Com
35、pilation_Units;with Check_Compilation_Unit;procedure My_Application isMy_Context : Asis.Context;beginAsis.Implementation.Initialize;Asis.Ada_Environments.Associate (My_Context, “);Asis.Ada_Environments.Open (My_Context);Asis.Ada_Environments.Close (My_Context);Asis.Ada_Environments.Dissociate (My_Co
36、ntext);Asis.Implementation.Finalize; end My_Application;,ASIS Application Template (1 of 5),ASIS Application Template (2 of 5) ,declareUnit_List : constant Asis.Compilation_Unit_List := Asis.Compilation_Units.Compilation_Units (My_Context);beginfor I in Unit_ListRange loopcase Asis.Compilation_Units
37、.Unit_Origin (Unit_List (I) iswhen Asis.An_Application_Unit =Check_Compilation_Unit.Perform_ASIS_Analysis (Unit_List (I);when others = null;end case;end loop;end;,ASIS Application Template (3 of 5) Package Check_Compilation_Unit,with Asis; package Check_Compilation_Unit isprocedure Perform_ASIS_Anal
38、ysis (CU : in Asis.Compilation_Unit);end Check_Compilation_Unit;,ASIS Application Template (4 of 5) Package Body,with Asis; with Asis.Elements; with Asis.Iterator; with with Ada.Wide_Text_Io; use Ada.Wide_Text_Io; package body Check_Compilation_Unit isprocedure Process_Element (An_Element : in Asis.
39、Element;Control : in out Asis.Traverse_Control;Dummy : in out boolean);procedure No_Op (An_Element : in Asis.Element;Control : in out Asis.Traverse_Control;Dummy : in out boolean);procedure Analyze_Unit is new Asis.Iterator.Traverse_Element(boolean, Process_Element, No_Op);Procedure Perform_ASIS_Ana
40、lysis (CU : Asis.Compilation_Unit) isControl : Asis.Traverse_Control := Asis.Continue;Dummy : boolean;beginPut_Line (“Processing Unit:“ ,See Next Page,Body of No_Op is null,ASIS Application Template (5 of 5) Process_Element,procedure Process_Element (An_Element : in Asis.Element;Control : in out Asi
41、s.Traverse_Control;Dummy : in out boolean) isbegin- Perform_Information_Flow_Analysis_Identify_Declarations (An_Element); - Example 1.- Perform Control_Flow_Analysis_Generate_Call_Tree (An_Element); - Example 2.- Perform Formal_Code_Verification_Restrictions_Checks_Check_Library_Level_Task(An_Elemen
42、t); - Example 3.- Perform Metrics Analysis.end Process_Element;,Note: this approach is valuable if a report is to be produced for each analysis. In the simple example provided, the printed output would be interleaved.,Example 1 : Identify Declarations for Information Flow Analysis - 1,procedure Iden
43、tify_Declarations (An_Element : in Asis.Element) ispackage Kind_Io is new Ada.Wide_Text_Io.Enumeration_Io (Asis.Declaration_Kinds);Decl_Kind : Asis.Declaration_Kinds := Asis.Elements.Declaration_Kind (An_Element);begincase Decl_Kind iswhen Asis.Not_A_Declaration = null;when others =declareName_List
44、: Asis.Defining_Name_List := Asis.Declarations.Names (An_Element);beginfor I in Name_ListRange loopPut (Asis.Declarations.Defining_Name_Image (Name_List (I);Put (“ (is kind) “);Kind_Io.Put (Decl_Kind);New_Line;end loop;end;end case;end Identify_Declarations;,For =package Asis_Test istype T is ( A, B
45、, C);S : integer := TBASESIZE ;end Asis_Test ;,Result =Processing Unit: Asis_Test Asis_Test (is kind) A_PACKAGE_DECLARATION T (is kind) AN_ORDINARY_TYPE_DECLARATION A (is kind) AN_ENUMERATION_LITERAL_SPECIFICATION B (is kind) AN_ENUMERATION_LITERAL_SPECIFICATION C (is kind) AN_ENUMERATION_LITERAL_SP
46、ECIFICATION S (is kind) A_VARIABLE_DECLARATION,Other Analysis Alternatives,Decl_Kind from example is of type Declaration_Kinds defined in Subclause 3.9.4 Queries on Declaration_Kinds are found in Asis.Declarations (Clause 15)General Element processing queries in Asis.Elements (Clause 13)Similar synt
47、actic processing can be performed on other Element Kinds defined in 3.9:,Example 1 : Identify Declarations for Information Flow Analysis - 2,Notes for extending capability for analysis of when objects are read and set:1. ASIS has capability to hyperlink to original declaration (unwinding throughrena
48、mings through a number of different packages may be required) My_Object_Declaration := Asis.Expressions.Corresponding_Name_Declaration (My_Object);2. ASIS has capability to compare elements to see if they are identical Asis.Elements.Is_Identical (My_Object_Declaration, Variable_Declaration(I)3. ASIS
49、 has capability for unique, persistent ids, valid until active partition is recompiled (Useful for sharing information between tools) Unique_Persistent_ID := Asis.Ids.Create_Id (An_Element);4. ASIS can easily obtain line numbers or textual span of elements Line_Number := Asis.Text.First_Line_Number (My_Object);Span := Asis.Text.Span (My_Object_Declaration);For example, span of Decl_Kinds Object Declaration is logically: Decl_Kind : Asis.Declaration_Kinds := Asis.Elements.Declaration_Kind (An_Element);,