Experimental Validation of Large-Scale Networked Software Systems

NSF 0086096

About the Project

The “Experimental Validation of Large-Scale Networked Software Systems” project was supported by the Information Technology Research (ITR) program of the National Science Foundation under contract number 0086096. It was a joint effort of four research groups at the University of Illinois.

People

• Prof. William H. Sanders (Principal Investigator) and his students:
  • Kaustubh R. Joshi
  • Ryan Lefever
• Prof. Wen-mei W. Hwu and his students:
  • Ron Barnes
  • Hong-Seok Kim
• Prof. Ravishankar K. Iyer and his team:
  • Shuo Chen
  • Michael Hamman
  • Zbigniew Kalbarczyk
  • Zhenyu Yang
• Prof. Steven S. Lumetta and his student:
  • Honghai Zhang

Background

Large-scale networked software systems are hard to design, and even more difficult to validate. Validation of such systems is increasingly important, since they are more and more being called on to perform critical functions. This validation difficulty stems from the inherent complexity of these systems, and often is due to the fact that they are often designed to adapt to variable workloads and operating conditions at the process, node, and network levels. Incorrect operation during periods of dynamic adaptation can lead to unpredictable and potentially hazardous consequences. In order to ensure that such systems operate correctly in critical environments, one must perform validations to confirm that they will function reliably in the presence of faults/failures, have predictable performance, and will continue to operate when intrusions occur. Validation of multiple behavior dimensions (e.g., reliability/availability, performance, and survivability) is also critical. This research developed the theory, methodology, and tools necessary to experimentally validate the reliability/availability, performance, and survivability of large-scale networked software systems. The intention was to develop a comprehensive framework for experimentally validating large-scale networked software systems. Taken as a whole, this work provided a sound and fundamental approach to validation of networked software and applications.

---

Papers generated by the project

This material is based upon work supported by the National Science Foundation under Grant No. 0086096. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the National Science Foundation.

• S. Bagchi, Y. Liu, K. Whisnant, Z. Kalbarczyk, R. Iyer, Y. Levendel, and L. Votta, “A Framework for Database Audit and Control Flow Checking for a Wireless Telephone Network Controller,” Proc. of the International Conference on Dependable Systems and Networks, DSN’01, July 1-4, 2001, p. 225-234. [IEEE Xplore entry]
• R. Barnes, Extracting Hardware-Detected Program Phases for Post-Link Optimization. M.S. Thesis, University of Illinois at Urbana-Champaign, 2002.
• R. D. Barnes, M. T. Conte, E. M. Nystrom, and W. W. Hwu, “Phase Profiling in a Managed Code Environment,” Proceedings of the First Workshop on Managed Run Time Environment Workloads, 2003.
• R. D. Barnes, E. M. Nystrom, M. C. Merten and W. W. Hwu, “Vacuum Packing: Extracting Hardware-Detected Program Phases for Post-link Optimization,” Proc. 35th Annual IEEE/ACM International Symposium on Microarchitecture, Nov. 2002, pp. 233-244. [IEEE Xplore entry]
• C. Basile, Z. Kalbarczyk, and R. Iyer, “A Preemptive Deterministic Scheduling Algorithm for Multithreaded Replicas,” Proceedings of the International Conference on Dependable Systems and Networks (DSN), June 22-25, 2003, pp. 149-158. [IEEE Xplore entry]
• C. Basile, L. Wang, Z. Kalbarczyk, and R. Iyer, “Group Communication Protocols under Errors,” Proc. of Symposium on Reliable Distributed Systems (SRDS ’03), Oct. 6-18, 2003, pp. 35-44. [IEEE Xplore entry]
• D. J. Beauregard, Z. Kalbarczyk, R. K. Iyer, S. Chau, and L. Alkalai, “Error-Injection-Based Failure Characterization of the IEEE 1394 Bus,” Proceedings of the 9th IEEE On-Line Testing Symposium (IOLTS), July 7-9, 2003, pp. 202-206. [IEEE Xplore entry]
• P. Buchholz and W. H. Sanders, “Approximate Computation of Transient Results for Large Markov Chains,” Proceedings of the 1st International Conference on Quantitative Evaluation of Systems (QEST 2004), Enschede, The Netherlands, September 27-30, 2004, pp. 126-135. [IEEE Xplore entry]
• R. Chandra, R. M. Lefever, K. R. Joshi, M. Cukier, and W. H. Sanders, “A Global-State-Triggered Fault Injector for Distributed System Evaluation,” IEEE Transactions on Parallel and Distributed Systems, vol. 15, no. 7, July 2004, pp. 593-605. [IEEE Xplore entry]
• S. Chen, J. Xu, R. K. Iyer, and K. Whisnant, “Evaluating the Security Threat of Firewall Data Corruption Caused by Instruction Transient Errors,” Proc. of the International Conference on Dependable Systems and Networks (DSN 2002), Washington DC, June 2002, pp. 495-504. [IEEE Xplore entry]
• S. Chen, J. Xu, Z. Kalbarczyk, R. K. Iyer, and K. Whisnant, “Modeling and Evaluating the Security Threats of Transient Errors in Firewall Software,” International Journal on Performance Evaluation, vol. 56, 2004.
• M. Conte, A Dynamic Application Analysis Framework. Ph.D. Thesis, University of Illinois at Urbana-Champaign, 2003.
• T. Courtney, D. Daly, S. Derisavi, S. Gaonkar, M. Griffith, V. Lam, and W. H. Sanders, “The Möbius Modeling Environment: Recent Developments,” Proceedings of the 1st International Conference on Quantitative Evaluation of Systems (QEST 2004), Enschede, The Netherlands, September 27-30, 2004, pp. 328-329. [IEEE Xplore entry]
• T. Courtney, D. Daly, S. Derisavi, V. Lam, and W. H. Sanders, “The Möbius Modeling Environment,” in Tools of the 2003 Illinois International Multiconference on Measurement, Modelling, and Evaluation of Computer-Communication Systems, Universität Dortmund Fachbereich Informatik research report no. 781/2003, 2003, pp. 34-37.
• T. Courtney, S. Derisavi, S. Gaonkar, M. Griffith, V. Lam, M. McQuinn, E. Rozier, and W. H. Sanders, “The Möbius Modeling Environment: Recent Extensions – 2005,” Proceedings of the 2nd International Conference on the Quantitative Evaluation of Systems (QEST), Torino, Italy, September 19-22, 2005, pp. 259-260. [IEEE Xplore entry]
• D. M. Daly, Bounded Aggregation Techniques to Solve Large Markov Models. Doctoral Dissertation, University of Illinois, 2005.
• D. Daly, P. Buchholz, and W. H. Sanders, “An Approach for Bounding Reward Measures in Markov Models Using Aggregation,” University of Illinois at Urbana-Champaign Coordinated Science Laboratory technical report UILU-ENG-04-2206 (CRHC-04-06), July 2004.
• L. de Moura and H. Ruess, “Lemmas on Demand for Satisfiability Solvers,” Annals of Mathematics and Artificial Intelligence, to appear.
• L. de Moura, H. Ruess, and M. Sorea, “Lazy Theorem Proving for Bounded Model Checking over Infinite Domains,” Proc. International Conference on Automated Deduction (CADE 2002), LNAI 2392, Springer-Verlag.
• S. Derisavi, The Möbius State-Level Abstract Functional Interface. Master’s Thesis, University of Illinois, 2003.
• S. Derisavi, Solution of Large Markov Models Using Lumping Techniques and Symbolic Data Structures. Doctoral Dissertation, University of Illinois, 2005.
• S. Derisavi, H. Hermanns, and W. H. Sanders, “Optimal State-Space Lumping in Markov Chains,” Information Processing Letters, vol. 87, no. 6, September 30, 2003, pp. 309-315.
• S. Derisavi and P. Kemper, “Integrating Analysis Techniques in Möbius: Experiences with Interfaces,” Proceedings of ICALP 2003 Satellite Workshop on Stochastic Petri Nets and Related Formalisms (Universität Dortmund Research Report No. 780), Eindhoven, The Netherlands, June 28-29, 2003, p. 170.
• S. Derisavi, P. Kemper, and W. H. Sanders, “Lumping Matrix Diagram Representations of Markov Models,” Proceedings of the 2005 International Conference on Dependable Systems and Networks (DSN-2005), Yokohama, Japan, June 28-July 1, 2005, pp. 742-751. [IEEE Xplore entry]
• S. Derisavi, P. Kemper, and W. H. Sanders, “Symbolic State-space Exploration and Numerical Analysis of State-sharing Composed Models,” Proceedings of NSMC ’03: The Fourth International Conference on the Numerical Solution of Markov Chains, Urbana, IL, USA, September 3-5, 2003, pp. 167-189.
• S. Derisavi, P. Kemper, and W. H. Sanders, “Symbolic State-space Exploration and Numerical Analysis of State-sharing Composed Models,” Linear Algebra and Its Applications (LAA), vol. 386, July 15, 2004, pp. 137-166.
• G. F. Frehse, O. Stursberg, S. Engell, R. Huuck, and B. Lukoschus, “Verification of Hybrid Controlled Processing Systems based on Decomposition and Deduction,” Proc. 2001 IEEE International Symposium on Intelligent Control (ISIC 2001), pp. 150-155. [IEEE Xplore entry]
• S. Gaonkar, Exploring Design Configurations of System Models: From Simultaneous Simulation to Search Heuristics. Ph.D. Dissertation, University of Illinois at Urbana-Champaign, 2008.
• S. Gaonkar and W. H. Sanders, “Simultaneous Simulation of Alternative System Configurations,” Proceedings of the 11th Pacific Rim International Symposium on Dependable Computing, Changsha, Hunan, China, Dec. 12-14, 2005, pp. 41-48. [IEEE Xplore entry]
• G. Godoy, A. Tiwari, and R. Nieuwenhuis, “Classes of Term Rewrite Systems with Polynomial Confluence Problems,” ACM Transactions on Computational Logic (TOCL), vol. 5(2), 2004.
• W. Gu, Z. Kalbarczyk, R. K. Iyer, and Z. Yang, “Characterization of Linux Kernel Behavior under Errors,” Proceedings of the International Conference on Dependable Systems and Networks (DSN’03), 2003, pp. 459-468. [IEEE Xplore entry]
• W. W. Hwu, D. I. August, and J. W. Sias, “Program Decision Logic Optimization Using Predication and Control Speculation,” Proceedings of the IEEE, vol. 89, no. 11, November 2001, pp. 1660-1675. [IEEE Xplore entry]
• R. K. Iyer, W. H. Sanders, J. H. Patel, and Z. Kalbarczyk, “The Evolution of Dependable Computing at the University of Illinois,” in R. Jacquart, Ed., Building the Information Society: IFIP 18th World Computer Congress Topical Sessions, Toulouse, France, August 22-27, 2004, pp. 135-164. Boston: Kluwer Academic Publishers.
• K. R. Joshi, Evaluating Unavailability Caused by Group Membership Using Global-State-Based Fault Injection. Master’s Thesis, University of Illinois, 2003.
• K. R. Joshi, Stochastic-Model-Driven Adaptation and Recovery in Distributed Systems. Doctoral Dissertation, University of Illinois, 2007.
• K. R. Joshi, M. Cukier, and W. H. Sanders, “Experimental Evaluation of the Unavailability Induced by a Group Membership Protocol,” Dependable Computing EDCC-4: Proceedings of the 4th European Dependable Computing Conference, Toulouse, France, October 23-25, 2002, pp. 140-158.
• Z. Kalbarczyk, R. K. Iyer, and L. Wang, “Application Fault Tolerance with Armor Middleware,” IEEE Internet Computing, vol. 9(2), 2005, p. 28-37. [IEEE Xplore entry]
• H.-S. Kim, Compaction Algorithm for Precise Modular Context-Sensitive Pointer Analysis. Ph.D. thesis, University of Illinois at Urbana-Champaign, 2004.
• T. Kim, D. Stringer-Calvert, and S.-D. Cha, “Formal Verification of Functional Properties of SCR-style Software Requirements Specification using PVS,” Proc. 8th International Conference on Tools and Algorithms for the Construction and Analysis of Systems (TACAS 2002), Springer LNCS vol. 2280, p. 205-220.
• V. V. Lam, A Path-Based Framework for Analyzing Large Markov Models. Ph.D. Dissertation, University of Illinois at Urbana-Champaign, 2011.
• V. V. Lam, P. Buchholz, and W. H. Sanders, “A Component-Level Path-Based Simulation Approach for Efficient Analysis of Large Markov Models,” Proceedings of the 2005 Winter Simulation Conference, Orlando, Florida, December 4-7, 2005, pp. 584-590. [IEEE Xplore entry]
• V. V. Lam, P. Buchholz, and W. H. Sanders, “A Structured Path-Based Approach for Computing Transient Rewards of Large CTMCs,” Proceedings of the 1st International Conference on Quantitative Evaluation of Systems (QEST), Enschede, The Netherlands, September 27-30, 2004, pp. 136-145. [IEEE Xplore entry]
• R. M. Lefever, Diverse Partial Memory Replication, Ph.D. thesis, University of Illinois at Urbana-Champaign, 2011.
• R. M. Lefever, An Experimental Evaluation of the Coda Distributed File System Using the Loki State-Driven Fault Injector. Master’s Thesis, University of Illinois, 2003.
• R. M. Lefever, M. Cukier, and W. H. Sanders, “An Experimental Evaluation of Correlated Network Partitions in the Coda Distributed File System,” Proceedings of the 22nd International Symposium on Reliable Distributed Systems (SRDS’03), Florence, Italy, October 6-8, 2003, pp. 273-282. [IEEE Xplore entry]
• S. S. Lumetta, “Detection of Synchronization Errors through Speculative Lock Elision,” Fast Abstract in Supplement of the 2002 International Conference on Dependable Systems and Networks, DSN-2002, Bethesda, Maryland, June 2002.
• S. S. Lumetta, S. J. Patel, B. Fahs, and S. Bose, “Symbolic Verification of Dynamic Optimization in Microprocessors (Fast Abstract),” Supplement of the 2001 International Conference on Dependable Systems and Networks (DSN-2001), Gothenberg, Sweden, July 2001, p. B30.
• J. Matarazzo, Study of Tunneling Opportunities and Concerns with Dynamically Linked Software. M.S. thesis, University of Illinois at Urbana-Champaign, 2001.
• M. Merten, Run-Time Optimization Architecture. Ph.D. thesis, University of Illinois at Urbana-Champaign, 2002.
• M. C. Merten, A. R. Trick, R. D. Barnes, E. M. Nystrom, C. N. George, J. C. Gyllenhall, and W. W. Hwu, “An Architectural Framework for Runtime Optimization,” IEEE Transactions on Computers, vol. 50, no. 6, June 2001, pp. 567-589. [IEEE Xplore entry]
• M. O. Moller, H. Rueß, and M. Sorea, “Predicate Abstraction for Dense Real-Time Systems,” Proc. Workshop on Theory and Practice of Timed Systems 2002, Electronic Notes in Theoretical Computer Science, vol. 65, 2002.
• E. Nystrom, Architectural Support for Persistent, Dynamic Code Transformation. M.S. thesis, University of Illinois at Urbana-Champaign, 2002.
• E. Nystrom, Fulcra Pointer Analysis Framework. Ph.D. thesis, University of Illinois at Urbana-Champaign, 2005.
• E. M. Nystrom, R. D. Barnes, M. C. Merten, and W. W. Hwu, “Code Reordering and Speculation Support for Dynamic Optimization Systems,” Proc. 2001 International Conference on Parallel Architectures and Compilation Techniques, September 2001, pp. 163-174. [IEEE Xplore entry]
• E. M. Nystrom, H.-S. Kim, and W.-M. Hwu, “Bottom-up and Top-down Context-Sensitive Summary-based Pointer,” Proceedings of the 11th Static Analysis Symposium, Florence, Italy, 2004.
• E. Nystrom, H.-S. Kim, and W.-m. Hwu, “Importance of Heap Specialization in Pointer Analysis,” Proceedings of PASTE’04, Washington DC, 2004.
• J. Rushby, “An Overview of Formal Verification for the Time-Triggered Architecture Formal Techniques in Real-Time and Fault-Tolerant Systems (FTRTFT),” Proceedings of Formal Techniques in Real-Time and Fault-Tolerant Systems 7th International Symposium, FTRTFT 2002, Oldenburg, Germany, September 9-12, 2002, Springer LNCS, vol. 2469, 2002.
• W. H. Sanders, “Cooperative Research in Multi-Formalism, Multi-Solution Modeling: Opportunities and Challenges” (keynote address), Proceedings of ICALP 2003 Satellite Workshop on Stochastic Petri Nets and Related Formalisms (Universität Dortmund Research Report No. 780), Eindhoven, The Netherlands, June 28-29, 2003, p. 170.
• A. Sharma, J. R. Martin, N. Anand, M. Cukier, and W. H. Sanders, “Ferret: A Host Vulnerability Checking Tool,” Proceedings of the 10th IEEE Pacific Rim International Symposium on Dependable Computing (PRDC-10), Papeete, Tahiti, French Polynesia, March 3-5, 2004, pp. 389-394. [IEEE Xplore entry]
• S. Singh, J. Lyons, and D. M. Nicol, “Fast Model-Based Penetration Testing,” Proc. 2004 Winter Simulation Conference (WSC’04), Washington, DC, December 5-8, 2004, pp. 309-317. [IEEE Xplore entry]
• M. Sorea, “A Decidable Fixpoint Logic for Time-Outs,” Proceedings of the 13th International Conference on Concurrency Theory (CONCUR), Springer LNCS, vol. 2421, 2002.
• M. Sorea, “TEMPO: A Model Checker for Event-Recording Automata,” Proc. Workshop on Real-Time Tools (RT-TOOLS) 2001 (Affiliated to CONCUR), 2001.
• A. Tiwari, “Deciding Confluence of Certain Term Rewriting Systems in Polynomial Time,” Proc. IEEE Symposium on Logic in Computer Science (LICS 2002), 2002, pp. 447-457. [IEEE Xplore entry]
• D. Varro, “A Formal Semantics of UML Statecharts by Model Transition Systems,” Proceedings of the First International Conference on Graph Transformation (ICGT), Springer LNCS, vol. 2505, 2002.
• D. Varro, “Towards Symbolic Analysis of Visual Modeling Languages,” Graph Transformation and Visual Modeling Techniques (GT-VMT) (Paolo Bottoni and Mark Minas, Eds.), Electronic Notes in Theoretical Computer Science, vol. 72, 2003.
• D. Varro and A. Pataricza, “Metamodeling Mathematics: A Precise and Visual Framework for Describing Semantics Domains of UML Models,” UML 2002 – The Unified Modeling Language (J.-M. Jezequel, H. Hussmann, and S. Cook, Eds.), Springer LNCS, vol. 2460, 2002.
• K. Whisnant, R. K. Iyer, P. Jones, R. Some, and D. Rennels, “An Experimental Evaluation of the REE SIFT Environment for Spaceborne Applications,” Proc. of the International Conference on Dependable Systems and Networks (DSN’02), 2002, pp. 585-594. [IEEE Xplore entry]
• K. Whisnant, R. K. Iyer, Z. Kalbarczyk, P. H. Jones III, D. A. Rennels, and R. Some, “The Effects of an ARMOR-Based SIFT Environment on the Performance and Dependability of User Applications,” IEEE Transactions on Software Engineering, vol. 30(4), 2004, p. 257-277. [IEEE Xplore entry]
• J. Xu, S. Chen, Z. Kalbarczyk, and R. K. Iyer, “An Experimental Study of Security Vulnerabilities Caused by Errors,” Proc. of the International Conference on Dependable Systems and Networks (DSN’01), Göteborg, Sweden, June 30-July 4, 2001, pp. 421-430. [IEEE Xplore entry]