Transcription
DOT/FAA/TC-14/49Federal Aviation AdministrationWilliam J. Hughes Technical CenterAviation Research DivisionAtlantic City International AirportNew Jersey 08405Selection ofCyclic Redundancy Code andChecksum Algorithms toEnsure Critical Data IntegrityMarch 2015Final ReportThis document is available to the U.S. publicthrough the National Technical InformationServices (NTIS), Springfield, Virginia 22161.U.S. Department of TransportationFederal Aviation Administration
NOTICEThis document is disseminated under the sponsorship of the U.S.Department of Transportation in the interest of information exchange.The U.S. Government assumes no liability for the contents or use thereof.The U.S. Government does not endorse products or manufacturers.Trade or manufacturers’ names appear herein solely because they areconsidered essential to the objective of this report. The findings andconclusions in this report are those of the author(s) and do not necessarilyrepresent the views of the funding agency. This document does notconstitute FAA policy. Consult the FAA sponsoring organization listed onthe Technical Documentation page as to its use.This report is available at the Federal Aviation Administration William J.Hughes Technical Center’s Full-Text Technical Reports page:actlibrary.tc.faa.gov in Adobe Acrobat portable document format (PDF).
Technical Report Documentation Page1. Report No.2. Government Accession No.3. Recipient's Catalog No.DOT/FAA/TC-14/494. Title and Subitle5. Report DateSELECTION OF CYCLIC REDUNDANCY CODE AND CHECKSUMALGORITHMS TO ENSURE CRITICAL DATA INTEGRITYMarch 20157. Author(s)8. Performing Organization Report No.6. Performing Organization Code220410Philip Koopman1, Kevin Driscoll2, Brendan Hall29. Performing Organization Name and Address10. Work Unit No. (TRAIS)1Carnegie Mellon University5000 Forbes Ave., Pittsburgh, PA 15213 USA2Honeywell Laboratories1985 Douglas Drive North, Golden Valley, MN 55422 USA11. Contract or Grant No.12. Sponsoring Agency Name and Address13. Type of Report and Period CoveredU.S. Department of TransportationFederal Aviation Administration950 L’Enfant Plaza SW, 5th FloorWashington, DC 20024Final Report, August 2011-April 2013DTFACT-11-C-0000514. Sponsoring Agency Code\AIR-13415. Supplementary NotesThe Federal Aviation Administration Aviation Research Division COR was Charles Kilgore.16. AbstractThis report explores the characteristics of checksums and cyclic redundancy codes (CRCs) in an aviation context. It includes aliterature review, a discussion of error detection performance metrics, a comparison of various checksum and CRC approaches,and a proposed methodology for mapping CRC and checksum design parameters to aviation integrity requirements. Specificexamples studied are Institute of Electrical and Electronics Engineers (IEEE) 802.3 CRC-32; Aeronautical Radio, Incorporated(ARINC)-629 error detection; ARINC-825 Controller Area Network (CAN) error detection; Fletcher checksum; and theAeronautical Telecommunication Network (ATN)-32 checksum. Also considered are multiple error codes used together, specificeffects relevant to communication networks, memory storage, and transferring data from nonvolatile to volatile memory.Key findings include: (1) significant differences exist in effectiveness between error-code approaches, with CRCs being generallysuperior to checksums in a wide variety of contexts; (2) common practices and published standards may provide suboptimal (orsometimes even incorrect) information, requiring diligence in selecting practices to adopt in new standards and new systems;(3) error detection effectiveness depends on many factors, with the Hamming distance of the error code being of primaryimportance in many practical situations; (4) no one-size-fits-all error-coding approach exists, although this report does propose aprocedure that can be followed to make a methodical decision as to which coding approach to adopt; and (5) a number ofsecondary considerations must be taken into account that can substantially influence the achieved error-detection effectiveness of aparticular error-coding approach.17. Key Words18. Distribution StatementCRC, Cyclic redundancy code, Checksum, Error coding, Errordetection, Network data errors, Memory data errorsThis document is available to the U.S. public through theNational Technical Information Service (NTIS), Springfield,Virginia 22161. This document is also available from theFederal Aviation Administration William J. Hughes TechnicalCenter at actlibrary.tc.faa.gov.19. Security Classif. (of this report)UnclassifiedForm DOT F 1700.720. Security Classif. (of this page)Unclassified(8-72)Reproduction of completed page authorized21. No. of Pages11122. Price
ACKNOWLEDGEMENTSThe authors would like to thank the following people for their contributions to this project andthe underlying work upon which it was based: Justin Ray, Carnegie Mellon UniversityTheresa Maxino, Carnegie Mellon UniversityTridib Chakravarty, Carnegie Mellon UniversityPavan Allalaghatta, HoneywellThe authors would like to acknowledge the following Federal Aviation Administration ReviewTeam individuals for providing support to the project: Liz BrandliMichael P. DeWaltGary HoranCharles KilgoreBarbara LingbergSrini MandalapuSteve PaaschJohn StrasburgerWill StruckThe authors would also like to thank the anonymous contributors who provided valuableinformation during our industry data collection.iii/iv
TABLE OF CONTENTSPageEXECUTIVE SUMMARYxi1.INTRODUCTION11.11.21.31122.METHODOLOGY AND VALIDITY22.12.2Fault Model and Undetected ErrorsError Detection Performance PurposeBackgroundRelated Activities, Documents, Symbology, and TerminologyCoding Design ParametersPotential Evaluation CriteriaApplication AttributesOther FactorsThe Adopted Fault ModelChecksum EvaluationThe CRC EvaluationOther Evaluations571011CHECKSUM AND CRC ERROR DETECTION113.13.23.33.43.53.63.73.83.93.10Random Hash HD 1 Error DetectionParityLongitudinal Redundancy CheckTwo’s Complement ChecksumOne’s Complement ChecksumFletcher ChecksumAdler ChecksumThe ATN-32The CRCOther Error-Detection Considerations111213151617212224273.10.1 Effect of Initial Seed Values3.10.2 Burst Error Detection3.10.3 Detection of Changes in Data Order272728AVIATION-SPECIFIC RESULTS28v
4.14.25.6.The ARINC-629The ARINC-8252929FRAMING, ENCODING, AND MULTIPLE CRCS305.15.25.35.45.55.65.730303131323232Corrupted Length FieldBit Stuff VulnerabilitiesBalance Bit EncodingData ScramblersEncryptionMemory Data Placement EffectsMultiple Checksums and CRCSMAPPING CRITICALITY TO INTEGRITY COVERAGE336.16.26.36.46.56.6Importance of Coverage DeterminationScopeData-Transfer System Guidance BackgroundMapping Process OverviewExample Avionics Data-Transfer SystemCriticality Mapping Flow, Steps A and B3334353536376.6.137Criticality Mapping Flow, Steps A and B Example6.7 Criticality Mapping Flow, Step C6.86.96.106.11376.7.1 Criticality Mapping Flow, Step C Example37Criticality Mapping Flow, Step D376.8.138Criticality Mapping Flow, Step D ExampleCriticality Mapping Flow, Step E.386.9.16.9.26.9.36.9.439404041Finding a BERThe BER TestsThe BER DegradationCriticality Mapping Flow, Step E ExampleCriticality Mapping Flow, Step F416.10.1 Criticality Mapping Flow, Step F Example41Criticality Mapping Flow, Step G416.11.1 Criticality Mapping Flow, Step G Example41vi
6.126.136.146.156.166.176.18Criticality Mapping Flow, Step H426.12.1 Criticality Mapping Flow, Step H Example42Error Detection Mechanism FailureOther Errors in the MessageUsing HD To Exploit CRCSA Simplified Approach to CoverageData Storage ProtectionTransfer from NonVolatile to Program RAM4343444545467.FUTURE ICESA—Literature Review and DiscussionB—Seven Deadly Sins for Checksums and Cyclic Redundancy CodesC—Cyclic Redundancy Code and Checksum Tutorial Slidesvii
LIST OF FIGURESFigurePage1The Pud for LRC and Addition Checksums142The 32-Bit Checksum Performance203Fletcher Checksum Performance214The ATN-32 Checksum Algorithm225The 32-Bit Checksum Compared to ATN-32 Performance246A 32-Bit Error Code Performance Including CRC-32257Corruption of Message Length Field308Criticality Mapping Flow Diagram36viii
LIST OF TABLESTablePage1Random Hash Error Detection122The LRC Error Detection143Two's Complement Checksum Error Detection164One's Complement Checksum Error Detection175Fletcher Checksum Error Detection196The ATN-32 Checksum Error Detection237Error Detection of Good CRC Polynomials26ix
LIST OF ACRONYMS AND DLCHWIECIEEEIPKbytesAdvisory CircularAeronautical Radio, IncorporatedAeronautical Telecommunication NetworkBit error ratioController Area NetworkComité Consultatif International Téléphonique et TélégraphiqueCommercial, Off-the-ShelfCyclic redundancy codeFederal Aviation AdministrationFrame check sequenceHamming distanceHigh Level Data Link ControlHamming weightInternational Electrotechnical CommissionInstitute of Electrical and Electronics EngineersInternet protocolKilobytes (1024 bytes—since random-access memory capacity, such as CPU cachemeasurements are always stated in multiples of 1024 (210) bytes, due to memory'sbinary addressing)LFSRLinear feedback shift registerLRCLongitudinal redundancy checkMICMessage Integrity CheckModbusModicon busNRZNon-return-to-zeroNUREGNuclear Regulatory Commission publicationPROFIBUS Process field busPROFIsafe Process field bus safety profilePudProbability of undetected errorRAMRandom access memoryRFCRequest for commentRTCARTCA, Inc. (formerly Radio Technical Commission for Aeronautics)RZReturn-to-zeroSAESAE, Inc.SCTPStream Control Transmission ProtocolSILSafety Integrity LevelTCPTransmission Control ProtocolTTP/CTime-Triggered Protocol Version CUDPUser Datagram ProtocolXORExclusive ORx
EXECUTIVE SUMMARYThis report explores the characteristics of checksums and cyclic redundancy codes (CRCs) in anaviation context. It includes a literature review; a discussion of error detection performancemetrics; a comparison of various checksum and CRC approaches; and a proposed methodologyfor mapping CRC and checksum design parameters to aviation integrity requirements. Specificexamples studied are Institute of Electrical and Electronics Engineers (IEEE) Standard 802.3CRC-32; Aeronautical Radio, Incorporated (ARINC)-629 error detection; ARINC-825 ControllerArea Network error detection; Fletcher checksum; and the Aeronautical TelecommunicationNetwork-32 checksum. Also considered are multiple error codes used together, specific effectsrelevant to communication networks, memory storage, and transferring data from nonvolatile tovolatile memory.The key findings of the report show that: Significant differences in performance between error detection approaches, with CRCs, inmany cases, providing dramatically better error-detection capabilities than checksums. Common practice and published standards have suboptimal 1 (or sometimes incorrect)information about error detection codes. For example, Fletcher checksums are sometimessaid to be as good as a standard CRC, but are often dramatically less effective than awell-chosen CRC. This report provides state-of-the-art information in this area. Error detection effectiveness depends on multiple factors, including the size of data to beprotected, the types of data errors expected, the smallest number of bit errors that areundetectable by the error code (Hamming distance [HD]), and the undetected errorfraction of errors as a function of number of bit errors present in a particular piece of data. There is no one-size-fits-all answer as to which error detection code to use. In evaluatingerror detection capability, a recommended high-level approach is to: Understand the acceptable probability of undetected error (Pud) Characterize exposure to data faults Determine what fraction of dangerous faults will be undetected by a particular errorcode, given an appropriate fault model Determine if the Pud (based on both exposure to faults and fault detection rate) issufficiently low to meet integrity requirements1The use of the term “suboptimal,” when describing a technique, should not be interpreted as indicating that the technique is not suitable forparticular purposes.xi
In determining if undetected error probabilities are low enough, it can be sufficient to pick anerror code with an adequately large HD so that all errors expected to occur within a system'soperating life are guaranteed to be detected (so long as a random independent fault modelaccurately reflects the errors that will be seen in operation).There are a number of other considerations, constraints, and system-level issues that must beconsidered. These include: The need to scrub error detection mechanisms and data values to mitigate the risk of faultaccumulation over time Vulnerabilities due to message framing (e.g., corrupted length field undermining CRCeffectiveness) Vulnerabilities due to bit encoding (e.g., stuff bits, multi-bit symbols, or scramblingundermining CRC HD) Potential bit error correlations due to memory geometry Complex intermediate processing stages potentially invalidating an assumption ofunpatterned, random independent bit errorsxii
1. INTRODUCTION.1.1 PURPOSE.This document is the final report of a task to create a comparative summary of checksum andCyclic Redundancy Code (CRC) performance in an aviation context. Specific goals are toperform a literature review of evaluation criteria, parameters, and tradeoffs; study CRC andchecksum performance with respect to their design parameters and achieved error detectionperformance; recommend a way to relate CRC and checksum design parameters to functionalintegrity levels; and make recommendations for future research work.This report also briefly addresses additional areas vital to correct application of error detectioncodes in practice. These areas
4.1 The ARINC-629 29 4.2 The ARINC-825 29 5. FRAMING, ENCODING, AND MULTIPLE CRC. S. 30 5.1 Corrupted Length Field 30 5.2 Bit Stuff Vulnerabilities 30 5.3 Balance Bit Encoding 31 5.4 Data Scramblers 31 5.5 Encryption 32 5.6 Memory Data Placement Effects 32 5.7 Multiple Checksums and CRC. S. 32 6. MAPPING CRITICALITY TO INTEGRITY COVERAGE 33 6.1 Importance of Coverage
