logo

SCIENTIA SINICA Informationis, Volume 49, Issue 11: 1428-1450(2019) https://doi.org/10.1360/N112018-00305

Software testing for cyber-physical systems suffering uncertainty

More info
  • ReceivedNov 12, 2018
  • AcceptedAug 20, 2019
  • PublishedNov 8, 2019

Abstract

Cyber-physical systems (CPS) represent an important part of the software infrastructure in the ternary human-cyber-physical universe. In this new era, the CPS software should be continually adapting and evolving. Such constantly-growing CPS software is capable of handling emerging software environments, developing models, and executing platforms. However, environmental uncertainty poses challenges to CPS testing. In this article, the challenges of CPS testing caused by environmental uncertainty are studied. A comprehensive analysis of the impact of environmental uncertainty on CPS testing is conducted, and a research framework for effective and efficient testing CPS is proposed. Based on the proposed framework, the state-of-the-art testing CPS software is discussed, and three testing techniques that address environmental uncertainty are introduced, including a test input generation approach (SIT), a test oracle generation approach (CoMID), and an environmental suitability evaluation approach (SynEva). The experiments are conducted using an illustrative self-adaptive robot car, and the obtained experimental results show that the three proposed approaches can provide effective CPS testing.


Funded by

国家重点研发计划(2017YFB1001801)

国家自然科学基金(61932021,61902173)

软件新技术与产业化协同创新中心(江苏)


References

[1] Lü J, Ma X X, Tao X P, et al. A survey of Internetware: research and progress. Sci China Ser E-Inf Sci, 2006, 36: 1037--1080. Google Scholar

[2] Lü J, Ma X X, Huang Y, et al. Internetware: a shift of software paradigm. In: Proceedings of the 1st Asia-Pacific Symposium on Internetware (Internetware 2009), Beijing, 2009. Google Scholar

[3] Mei H, Huang G, Xie T. Internetware: A Software Paradigm for Internet Computing. Computer, 2012, 45: 26-31 CrossRef Google Scholar

[4] Dobson S, Denazis S, Fernández A. A survey of autonomic communications. ACM Trans Auton Adapt Syst, 2006, 1: 223-259 CrossRef Google Scholar

[5] Zhang J, Cheng B H. Model-based development of dynamically adaptive software. In: Proceedings of the 28th International Conference on Software Engineering, Shanghai, 2006. 371--380. Google Scholar

[6] Sama M, Elbaum S, Raimondi F. Context-Aware Adaptive Applications: Fault Patterns and Their Automated Identification. IIEEE Trans Software Eng, 2010, 36: 644-661 CrossRef Google Scholar

[7] Xu C, Cheung S C, Ma X. Adam: Identifying defects in context-aware adaptation. J Syst Software, 2012, 85: 2812-2828 CrossRef Google Scholar

[8] Garlan D. Software engineering in an uncertain world. In: Proceedings of FSE/SDP Workshop on Future of Software Engineering Research, 2010. 125--128. Google Scholar

[9] Elbaum S, Rosenblum D S. Known unknowns: testing in the presence of uncertainty. In: Proceedings of the 22nd ACM SIGSOFT International Symposium on Foundations of Software Engineering, 2014. 833--836. Google Scholar

[10] Esfahani N, Kouroshafar E, Malek S. Taming uncertainty in self-adaptive software. In: Proceedings of the 19th ACM SIGSOFT Symposium and the 13th European Conference on Foundations of Software Engineering, Szeged, 2011. 234--244. Google Scholar

[11] Yang W H, Xu C, Liu Y P, et al. Verifying self-adaptive applications suffering uncertainty. In: Proceedings of the 29th ACM/IEEE International Conference on Automated Software Engineering, Vasteras, 2014. 199--210. Google Scholar

[12] Ramirez A J, Jensen A C, Cheng B H, et al. Automatically exploring how uncertainty impacts behavior of dynamically adaptive systems. In: Proceedings of the 26th IEEE/ACM International Conference on Automated Software Engineering, 2011. 568--571. Google Scholar

[13] Qin Y, Xu C, Yu P. SIT: Sampling-based interactive testing for self-adaptive apps. J Syst Software, 2016, 120: 70-88 CrossRef Google Scholar

[14] Qin Y, Xie T, Xu C, et al. CoMID: context-based multi-invariant detection for monitoring cyber-physical software. 2018,. arXiv Google Scholar

[15] Qin Y, Wang H Y, Xu C, et al. SynEva: evaluating ML programs by mirror program synthesis. In: Proceedings of IEEE International Conference on Software Quality, Reliability and Security, Lisbon, 2018. 171--182. Google Scholar

[16] National Science Foundation. Cyber-Physical Systems. 2018. https://www.nsf.gov/pubs/2019/nsf19553/nsf19553.htm. Google Scholar

[17] Myers G J, Sandler C, Badgett T. The Art of Software Testing. Hoboken: John Wiley and Sons, 2011. Google Scholar

[18] Tesla. Tesla self-driving car. https://www.tesla.com/. Google Scholar

[19] Google. Google self-driving car. https://waymo.com/. Google Scholar

[20] Uber. Uber self-driving car. https://venturebeat.com/2019/04/26/5-companies-are-testing-55-self-driving-cars-in-pittsburgh/. Google Scholar

[21] Wolpert D H, Macready W G. No free lunch theorems for optimization. IEEE Trans Evol Computat, 1997, 1: 67-82 CrossRef Google Scholar

[22] Fredericks E M, DeVries B, Cheng B H. Towards run-time adaptation of test cases for self-adaptive systems in the face of uncertainty. In: Proceedings of the 9th International Symposium on Software Engineering for Adaptive and Self-Managing Systems, Hyderabad, 2014. 17--26. Google Scholar

[23] Amalfitano D, Fasolino A R, Tramontana P, et al. Considering context events in event-based testing of mobile applications. In: Proceedings of the 6th International Conference on Software Testing, Verification and Validation Workshops, Luxembourg, 2013. 126--133. Google Scholar

[24] Jang M, Kim J, Sohn J C. Simulation framework for testing context-aware ubiquitous applications. In: Proceedings of the 7th International Conference on Advanced Communication Technology, 2005. 1337--1340. Google Scholar

[25] Lu H, Chan W K, Tse T H. Testing context-aware middleware-centric programs: a data flow approach and an RFID-based experimentation. In: Proceedings of the 14th ACM SIGSOFT International Symposium on Foundations of Software Engineering, 2006. 242--252. Google Scholar

[26] Lu H, Chan W K, Tse T H. Testing pervasive software in the presence of context inconsistency resolution services. In: Proceedings of the 30th International Conference on Software Engineering, 2008. 61--70. Google Scholar

[27] Filieri A, Ghezzi C, Tamburrelli G. Run-time efficient probabilistic model checking. In: Proceedings of the 33rd International Conference on Software Engineering, 2011. 341--350. Google Scholar

[28] Sama M, Rosenblum D S, Wang Z, et al. Model-based fault detection in context-aware adaptive applications. In: Proceedings of the 16th ACM SIGSOFT International Symposium on Foundations of Software Engineering, 2008. 261--271. Google Scholar

[29] Wang Z, Elbaum S, Rosenblum D S. Automated generation of context-aware tests. In: Proceedings of the 29th International Conference on Software Engineering, 2007. 406--415. Google Scholar

[30] Griebe T, Gruhn V. A model-based approach to test automation for context-aware mobile applications. In: Proceedings of the 29th Annual ACM Symposium on Applied Computing, 2014. 420--427. Google Scholar

[31] Esfahani N, Malek S, Razavi K. GuideArch: guiding the exploration of architectural solution space under uncertainty. In: Proceedings of International Conference on Software Engineering, 2013. 43--52. Google Scholar

[32] Adamsen C Q, Mezzetti G, Moller A. Systematic execution of android test suites in adverse conditions. In: Proceedings of International Symposium on Software Testing and Analysis, Baltimore, 2015. 83--93. Google Scholar

[33] Anand S, Naik M, Harrold M J, et al. Automated concolic testing of smartphone apps. In: Proceedings of the 20th International Symposium on the Foundations of Software Engineering, Cary, 2012. Google Scholar

[34] Matinnejad R, Nejati S, Briand L C, et al. Automated test suite generation for time-continuous simulink models. In: Proceedings of the 38th International Conference on Software Engineering, Austin, 2016. 595--606. Google Scholar

[35] Barr E T, Harman M, McMinn P. The Oracle Problem in Software Testing: A Survey. IIEEE Trans Software Eng, 2015, 41: 507-525 CrossRef Google Scholar

[36] Tse T H, Yau S S. Testing context-sensitive middleware-based software applications. In: Proceedings of the 28th Annual International Computer Software and Applications Conference, Hong Kong, 2004. 458--466. Google Scholar

[37] Ernst M D, Perkins J H, Guo P J. The Daikon system for dynamic detection of likely invariants. Sci Comput Programming, 2007, 69: 35-45 CrossRef Google Scholar

[38] Csallner C, Tillmann N, Smaragdakis Y. DySy: dynamic symbolic execution for invariant inference. In: Proceedings of the 30th International Conference on Software Engineering, Leipzig, 2008. 281--290. Google Scholar

[39] Pastore F, Mariani L. ZoomIn: discovering failures by detecting wrong assertions. In: Proceedings of the 37th IEEE International Conference on Software Engineering, 2015. 66--76. Google Scholar

[40] Pacheco C, Ernst M D. Eclat: automatic generation and classification of test inputs. In: Proceedings of European Conference on Object-Oriented Programming, 2005. 504--527. Google Scholar

[41] Jiang H, Elbaum S, Detweiler C. Reducing failure rates of robotic systems though inferred invariants monitoring. In: Proceedings of IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), 2013. 1899--1906. Google Scholar

[42] Aliabadi M R, Kamath A A, Gascon-Samson J, et al. ARTINALI: dynamic invariant detection for cyber-physical system security. In: Proceedings of the 11th Joint Meeting on Foundations of Software Engineering, Paderborn, 2017. 349--361. Google Scholar

[43] Golombek R, Wrede S, Hanheide M, et al. Online data-driven fault detection for robotic systems. In: Proceedings of IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), San Francisco, 2013. 3011--3016. Google Scholar

[44] Steinbauer G, Mörth M, Wotawa F. Real-time diagnosis and repair of faults of robot control software. In: Proceedings of Robot Soccer World Cup, 2005. 13--23. Google Scholar

[45] Gillula J H, Tomlin C J. Reducing conservativeness in safety guarantees by learning disturbances online: iterated guaranteed safe online learning. In: Robotics: Science and Systems. Cambridge: MIT Press, 2013. Google Scholar

[46] Bojarski M, Del Testa D, Dworakowski D, et al. End to end learning for self-driving cars. 2016,. arXiv Google Scholar

[47] Julian K D, Lopez J, Brush J S, et al. Policy compression for aircraft collision avoidance systems. In: Proceedings of the 35th Digital Avionics Systems Conference, 2016. Google Scholar

[48] Pei K X, Cao Y Z, Yang J F, et al. Deepxplore: automated whitebox testing of deep learning systems. In: Proceedings of the 26th Symposium on Operating Systems Principles, Shanghai, 2017. Google Scholar

[49] Witten I H, Frank E, Hall M A, et al. Data Mining: Practical Machine Learning Tools and Techniques. San Francisco: Morgan Kaufmann, 2016. Google Scholar

[50] California Department of Motor Vehicles. Autonomous Vehicle Disengagement Reports 2018. https://www.dmv.ca.gov/portal/dmv/detail/vr/autonomous/disengagement_report_2018. Google Scholar

[51] McKeeman W M. Differential testing for software. Digit Tech J, 1998, 10: 100--107. Google Scholar

[52] Chen T Y, Cheung S C, Yiu S M. Metamorphic Testing: A New Approach for Generating Next Test Cases. Technical Report HKUST-CS98-01. 1998. Google Scholar

[53] Tian Y, Pei K, Jana S, et al. DeepTest: automated testing of deep-neural-network-driven autonomous cars. In: Proceedings of the 40th International Conference on Software Engineering, Gothenburg, 2018. 303--314. Google Scholar

[54] Kurakin A, Goodfellow I, Bengio S. Adversarial examples in the physical world. 2016,. arXiv Google Scholar

[55] Nguyen A, Yosinski J, Clune J. Deep neural networks are easily fooled: high confidence predictions for unrecognizable images. In: Proceedings of IEEE Conference on Computer Vision and Pattern Recognition, 2015. 427--436. Google Scholar

[56] Fredrikson M, Jha S, Ristenpart T. Model inversion attacks that exploit confidence information and basic countermeasures. In: Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security, 2015. 1322--1333. Google Scholar

[57] Katz G, Barrett C, Dill D L, Jet al. Reluplex: an efficient SMT solver for verifying deep neural networks. In: Proceedings of International Conference on Computer Aided Verification, 2017. 97--117. Google Scholar

[58] Huang X, Kwiatkowska M, Wang S, et al. Safety verification of deep neural networks. In: Proceedings of International Conference on Computer Aided Verification, 2017. 3--29. Google Scholar

[59] Pulina L, Tacchella A. An abstraction-refinement approach to verification of artificial neural networks. In: Proceedings of InInternational Conference on Computer Aided Verification, 2010. 243--257. Google Scholar

[60] Chen Z Q. Design and implementation of system of deep learning scenario adaptability analysis based on program synthesis. Dissertation for Bachelor Degree. Nanjing: Nanjing University, 2019. Google Scholar

[61] Ma Y S, Offutt J, Kwon Y R. MuJava: an automated class mutation system. Softw Test Verif Reliab, 2005, 15: 97-133 CrossRef Google Scholar

  • Figure 1

    Interaction between CPS software and its physical environment suffering uncertainty

  • Figure 2

    Research framework: testing CPS software suffering uncertainty

  • Figure 3

    (Color online) Overview of SIT: sample-based interactive testing

  • Figure 4

    (Color online) Overview of CoMID: context-based multi-invariant detection

  • Figure 5

    (Color online) Overview of SynEva: program-synthesis-based ML programs evaluation

  • Figure 6

    (Color online) (a) Robot car and (b) its running environment

  • Table 1   Environment classification for image sets in RQ3
    Environment Total images Images in the training set Images in the testing set Images in the balanced testing
    Clear 16703 15033 1670 194
    Dark 4353 3918 435 194
    Shadow 3514 3163 351 194
    Sunlight 1948 1754 194 194
  • Table 2   Comparison of detected bugs for SIT, RT and DSE
    Testing approach Detected bugs (percentage of test instances)
    SIT 154 (85.6%)
    RT 65 (36.1%)
    DSE 112 (62.2%)
  • Table 3   Overview of the generated invariants by the three approaches
    CoMID naïve p-context
    TP (%) FP (%) TP (%) FP (%) TP (%) FP (%)
    78.3 15.6 61.6 34.3 68.1 21.4
  • Table 4   SynEva's prediction on ML program's suitability to different envrionments
    Training environment Prediction accuracy (%) Average prediction accuracy (%)
    Clear 72.8 78.0
    Dark 88.0
    Shadow 76.1
    Sunlight 75.0

Copyright 2020 Science China Press Co., Ltd. 《中国科学》杂志社有限责任公司 版权所有

京ICP备18024590号-1