EUVIMEDEUVIMED entdecken
Crossref

Formal analysis of the compact positionreporting algorithm

Aaron Dutle, Mariano Moscato, Laura Titolo, César Muñoz, Gregory Anderson, François Bobot

Formal Aspects of Computing · 2021-01 · 33 (1) · 65-86

DOI: 10.1007/s00165-019-00504-0 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Formal Aspects of Computing, 2021-01. Verfasst von Aaron Dutle und 5 weiteren Autor:innen. Die Arbeit wurde bisher 12-mal zitiert (Crossref) und nennt 29 Literaturangaben.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

The Automatic Dependent Surveillance-Broadcast (ADS-B) system allows aircraft to communicate current state information, including position and velocity messages, to other aircraft in their vicinity and to ground stations. The Compact Position Reporting (CPR) algorithm is the ADS-B protocol responsible for the encoding and decoding of aircraft positions. CPR is sensitive to computer arithmetic since it relies on functions that are intrinsically unstable such as floor and modulus. In this paper, a formal verification of the CPR algorithm is presented. In contrast to previous work, the algorithm presented here encompasses the entire range of message types supported by ADS-B. The paper also presents two implementations of the CPR algorithm, one in double-precision floating-point and one in 32-bit unsigned integers, which are both formally verified against the real-number algorithm. The verification proceeds in three steps. For each implementation, a version of CPR, which is simplified and manipulated to reduce numerical instability and leverage features of the datatypes, is proposed. Then, the Prototype Verification System (PVS) is used to formally prove real conformance properties, which assert that the ideal real-number counterpart of the improved algorithm is mathematically equivalent to the standard CPR definition. Finally, the static analyzer Frama-C is used to verify software conformance properties, which say that the software implementation of the improved algorithm is correct with respect to its idealized real-number counterpart. In concert, the two properties guarantee that the implementation meets the original specification. The two implementations will be included in the revised version of the ADS-B standards document as the reference implementation of the CPR algorithm.

Zitieren

APA

Dutle, A., Moscato, M., Titolo, L., Muñoz, C., Anderson, G., & Bobot, F. (2021). Formal analysis of the compact positionreporting algorithm. Formal Aspects of Computing, 33(1), 65-86. https://doi.org/10.1007/s00165-019-00504-0

Vancouver

Dutle A, Moscato M, Titolo L, Muñoz C, Anderson G, Bobot F. Formal analysis of the compact positionreporting algorithm. Formal Aspects of Computing. 2021;33(1):65-86. doi:10.1007/s00165-019-00504-0

BibTeX
@article{Dutle2021,
  author = {Dutle, Aaron and Moscato, Mariano and Titolo, Laura and Muñoz, César and Anderson, Gregory and Bobot, François},
  title = {Formal analysis of the compact positionreporting algorithm},
  journal = {Formal Aspects of Computing},
  year = {2021},
  volume = {33},
  number = {1},
  pages = {65--86},
  doi = {10.1007/s00165-019-00504-0}
}
Kostenlos starten →