Phys: probabilistic physical unit assignment and inconsistency detection

ABSTRACT

Program variables used in robotic and cyber-physical systems often have implicit physical units that cannot be determined from their variable types. Inferring an abstract physical unit type for variables and checking their physical unit type consistency is of particular importance for validating the correctness of such systems. For instance, a variable with the unit of ‘meter’ should not be assigned to another variable with the unit of ‘degree-per-second’. Existing solutions have various limitations such as requiring developers to annotate variables with physical units and only handling variables that are directly or transitively used in popular robotic libraries with known physical unit information. We observe that there are a lot of physical unit hints in these softwares such as variable names and specific forms of expressions. These hints have uncertainty as developers may not respect conventions. We propose to model them with probability distributions and conduct probabilistic inference. At the end, our technique produces a unit distribution for each variable. Unit inconsistencies can then be detected using the highly probable unit assignments. Experimental results on 30 programs show that our technique can infer units for 159.3% more variables compared to the state-of-the-art with more than 88.7% true positives, and inconsistencies detection on 90 programs shows that our technique reports 103.3% more inconsistencies with 85.3% true positives.

References

1. Eric Allen, David Chase, Joe Hallett, Victor Luchangco, Jan-Willem Maessen, Sukyoung Ryu, Guy L Steele Jr, Sam Tobin-Hochstadt, Joao Dias, Carl Eastlund, et al. 2005. The Fortress language specification. Sun Microsystems 139 (2005), 140.
2. BIPM. 2006. Le Système international d’unités / The International System of Units (‘The SI Brochure’) (eighth ed.). Bureau international des poids et mesures. http: //www.bipm.org/en/si/si_brochure/
3. Percy Williams Bridgman. 1922. Dimensional Analysis. Yale University Press.
4. Anthony Cozzie, Frank Stratton, Hui Xue, and Samuel T. King. 2008. Digging for Data Structures. In 8th USENIX Symposium on Operating Systems Design and Implementation, OSDI 2008, December 8-10, 2008, San Diego, California, USA, Proceedings, Richard Draves and Robbert van Renesse (Eds.). USENIX Association, 255–266. http://www.usenix.org/events/osdi08/tech/full_papers/cozzie/cozzie. pdf
5. Laura Dietz, Valentin Dallmeier, Andreas Zeller, and Tobias Scheffer. 2009. Localizing Bugs in Program Executions with Graphical Models. In Advances in Neural Information Processing Systems 22: 23rd Annual Conference on Neural Information Processing Systems 2009. Proceedings of a meeting held 7-10 December 2009, Vancouver, British Columbia, Canada., Yoshua Bengio, Dale Schuurmans, John D. Lafferty, Christopher K. I. Williams, and Aron Culotta (Eds.). Curran Associates, Inc., 468–476. http://papers.nips.cc/paper/ 3792-localizing-bugs-in-program-executions-with-graphical-models
6. Philip J. Guo, Jeff H. Perkins, Stephen McCamant, and Michael D. Ernst. 2006. Dynamic Inference of Abstract Types. In Proceedings of the 2006 International Symposium on Software Testing and Analysis (ISSTA ’06). ACM, New York, NY, USA, 255–265.
7. S. Hangal and M. S. Lam. 2009. Automatic dimension inference and checking for object-oriented programs. In 2009 IEEE 31st International Conference on Software Engineering. 155–165.
8. Irfan Ul Haq, Juan Caballero, and Michael D. Ernst. 2015. Ayudante: identifying undesired variable interactions. In Proceedings of the 13th International Workshop on Dynamic Analysis, WODA@SPLASH 2015, Pittsburgh, PA, USA, October 26, 2015, Harry Xu and Walter Binder (Eds.). ACM, 8–13.
9. 2823366
10. Paul N. Hilfinger. 1988. An Ada Package for Dimensional Analysis. ACM Trans. Program. Lang. Syst. 10, 2 (April 1988), 189–203.
11. 42346
12. Lingxiao Jiang and Zhendong Su. 2006. Osprey: a practical type system for validating dimensional unit correctness of C programs. In 28th International Conference on Software Engineering (ICSE 2006), Shanghai, China, May 20-28, 2006.
13. 262–271.
14. Michael Karr and David B. Loveman, III. 1978. Incorporation of Units into Programming Languages. Commun. ACM 21, 5 (May 1978), 385–391.
15. Andrew Kennedy. 2009. Types for Units-of-Measure: Theory and Practice. In Central European Functional Programming School - Third Summer School, CEFP 2009, Budapest, Hungary, May 21-23, 2009 and Komárno, Slovakia, May 25-30, 2009, Revised Selected Lectures. 268–305.
16. Daphne Koller and Nir Friedman. 2009. Probabilistic Graphical Models - Principles and Techniques. MIT Press. http://mitpress.mit.edu/catalog/item/default.asp? ttype=2&tid=11886
17. Frank R. Kschischang, Brendan J. Frey, and Hans-Andrea Loeliger. 2001. Factor graphs and the sum-product algorithm. IEEE Trans. Information Theory 47, 2 (2001), 498–519.
18. Zhiqiang Lin, Junghwan Rhee, Chao Wu, Xiangyu Zhang, and Dongyan Xu. 2012. Discovering Semantic Data of Interest from Un-mappable Memory with Confidence. In 19th Annual Network and Distributed System Security Symposium, NDSS 2012, San Diego, California, USA, February 5-8, 2012. The Internet Society.
19. https://www.ndss-symposium.org/ndss2012/ discovering-semantic-data-interest-un-mappable-memory-confidence
20. V. Benjamin Livshits, Aditya V. Nori, Sriram K. Rajamani, and Anindya Banerjee. 2009. Merlin: specification inference for explicit information flow problems. In Proceedings of the 2009 ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI 2009, Dublin, Ireland, June 15-21, 2009, Michael Hind and Amer Diwan (Eds.). ACM, 75–86.
21. 1542485
22. Daniel Marjamaeki. 2013. Cppcheck - A tool for static C/C++ code analysis. http://cppcheck.sourceforge.net/
23. George A. Miller. 1995. WordNet: A Lexical Database for English. Commun. ACM 38, 11 (Nov. 1995), 39–41.
24. Sasa Misailovic. 2017. Probabilistic reasoning for analysis of approximate computations. In Proceedings of the 2017 International Conference on Compilers, Architectures and Synthesis for Embedded Systems, CASES 2017, Seoul, Republic of Korea, October 15-20, 2017. 4:1.
25. Joris Mooij. 2010. libDAI - A free and open source C++ library for Discrete Approximate Inference in graphical models. https://staff.fnwi.uva.nl/j.m.mooij/ libDAI/
26. Flemming Nielson, Hanne Riis Nielson, and Chris Hankin. 1999. Principles of program analysis. Springer.
27. John-Paul Ore, Sebastian G. Elbaum, and Carrick Detweiler. 2017. Dimensional inconsistencies in code and ROS messages: A study of 5.9M lines of code. In 2017 IEEE/RSJ International Conference on Intelligent Robots and Systems, IROS 2017, Vancouver, BC, Canada, September 24-28, 2017. IEEE, 712–718. 1109/IROS.2017.8202229
28. John-Paul Ore, Carrick Detweiler, and Sebastian Elbaum. 2017. Lightweight Detection of Physical Unit Inconsistencies Without Program Annotations. In Proceedings of the 26th ACM SIGSOFT International Symposium on Software Testing and Analysis (ISSTA 2017). ACM, New York, NY, USA, 341–351.
29. John-Paul Ore, Carrick Detweiler, and Sebastian Elbaum. 2017. Phriky-Units: A Lightweight, Annotation-free Physical Unit Inconsistency Detection Tool. In Proceedings of the 26th ACM SIGSOFT International Symposium on Software Testing and Analysis (ISSTA 2017). ACM, New York, NY, USA, 352–355.
30. Judea Pearl. 1986. Fusion, Propagation, and Structuring in Belief Networks. Artif. Intell. 29, 3 (1986), 241–288.
31. Morgan Quigley, Ken Conley, Brian Gerkey, Josh Faust, Tully Foote, Jeremy Leibs, Rob Wheeler, and Andrew Y Ng. 2009. ROS: an open-source Robot Operating System. In ICRA workshop on open source software, Vol. 3.2. Kobe, Japan, 5.
32. Veselin Raychev, Martin Vechev, and Andreas Krause. 2015. Predicting Program Properties from "Big Code". In Proceedings of the 42Nd Annual ACM SIGPLANSIGACT Symposium on Principles of Programming Languages (POPL ’15). ACM, New York, NY, USA, 111–124.
33. ROS Industrial Consortium. 2016. Current Members - ROS Industrial. http: //rosindustrial.org/ric/current-members
34. G. Rosu and Feng Chen. 2003. Certifying measurement unit safety policy. In 18th IEEE International Conference on Automated Software Engineering, 2003. Proceedings. 304–309.
35. Matthias Schabel and Steven Watanabe. 2010. Boost Units. http://www.boost. org/doc/libs/1_66_0/doc/html/boost_units.html
36. Don Syme, Luke Hoban, Tao Liu, Dmitry Lomov, James Margetson, Brian McNamara, Joe Pamer, Penny Orwick, Daniel Quirk, Chris Smith, et al. 2010. The F# 2.0 language specification. Microsoft, August (2010).

Index Terms

• Mathematics of computing

  • Probability and statistics

    • Probabilistic representations

      • Factor graphs

• Software and its engineering

  • Software creation and management

    • Software verification and validation

      • Software defect analysis

  • Software notations and tools

    • General programming languages

      • Language features

        • Abstract data types