A fault model and mutation testing of access control policies

ABSTRACT

To increase confidence in the correctness of specified policies, policy developers can conduct policy testing by supplying typical test inputs (requests) and subsequently checking test outputs (responses) against expected ones. Unfortunately, manual testing is tedious and few tools exist for automated testing of access control policies. We present a fault model for access control policies and a framework to explore it. The framework includes mutation operators used to implement the fault model, mutant generation, equivalent-mutant detection, and mutant-killing determination. This framework allows us to investigate our fault model, evaluate coverage criteria for test generation and selection, and determine a relationship between structural coverage and fault-detection effectiveness. We have implemented the framework and applied it to various policies written in XACML. Our experimental results offer valuable insights into choosing mutation operators in mutation testing and choosing coverage criteria in test generation and selection.

REFERENCES

• 1: OASIS eXtensible Access Control Markup Language (XACML). http://www.oasis-open.org/committees/xacml/, 2005.
• 2: Sun's XACML implementation. http://sunxacml.sourceforge.net/, 2005.
• 3: Allen Troy Acree, Jr., On mutation, Georgia Institute of Technology, Atlanta, GA, 1980
• 4: Timothy Alan Budd, Mutation analysis of program test data, Yale University, New Haven, CT, 1980
• 5: Byoungju Choi , Aditya P. Mathur, High-performance mutation testing, Journal of Systems and Software, v.20 n.2, p.135-152, Feb. 1993 [doi>10.1016/0164-1212(93)90005-I]
• 6: Nicodemos Damianou , Naranker Dulay , Emil Lupu , Morris Sloman, The Ponder Policy Specification Language, Proceedings of the International Workshop on Policies for Distributed Systems and Networks, p.18-38, January 29-31, 2001
• 7: R. A. DeMillo, R. J. Lipton, and F. G. Sayward. Hints on test data selection: Help for the practicing programmer. IEEE Computer, 11(4):34--41, April 1978.
• 8: Richard A. DeMillo , A. Jefferson Offutt, Constraint-Based Automatic Test Data Generation, IEEE Transactions on Software Engineering, v.17 n.9, p.900-910, September 1991 [doi>10.1109/32.92910]
• 9: Kathi Fisler , Shriram Krishnamurthi , Leo A. Meyerovich , Michael Carl Tschantz, Verification and change-impact analysis of access-control policies, Proceedings of the 27th international conference on Software engineering, May 15-21, 2005, St. Louis, MO, USA [doi>10.1145/1062455.1062502]
• 10: Vladimir N. Fleyshgakker , Stewart N. Weiss, Efficient mutation analysis: a new approach, Proceedings of the 1994 ACM SIGSOFT international symposium on Software testing and analysis, p.185-195, August 17-19, 1994, Seattle, Washington, United States [doi>10.1145/186258.187179]
• 11: Robert Geist , A. Jefferson Offutt , Frederick C. Harris, Jr., Estimation and Enhancement of Real-Time Software Reliability Through Mutation Analysis, IEEE Transactions on Computers, v.41 n.5, p.550-558, May 1992 [doi>10.1109/12.142681]
• 12: M. R. Girgis , M. R. Woodward, An integrated system for program testing using weak mutation and data flow analysis, Proceedings of the 8th international conference on Software engineering, p.313-319, August 28-30, 1985, London, England
• 13: M. M. Greenberg, C. Marks, L. A. Meyerovich, and M. C. Tschantz. The soundness and completeness of Margrave with respect to a subset of XACML. Technical Report CS-05-05, Department of Computer Science, Brown University, 2005.
• 14: M. Jean Harrold , Rajiv Gupta , Mary Lou Soffa, A methodology for controlling the size of a test suite, ACM Transactions on Software Engineering and Methodology (TOSEM), v.2 n.3, p.270-285, July 1993 [doi>10.1145/152388.152391]
• 15: Mark Hennessy , James F. Power, An analysis of rule coverage as a criterion in generating minimal test suites for grammar-based software, Proceedings of the 20th IEEE/ACM international Conference on Automated software engineering, November 07-11, 2005, Long Beach, CA, USA [doi>10.1145/1101908.1101926]
• 16: J. R. Horgan and A. P. Mathur. Weak mutation is probably strong mutation. Technical Report SERC-TR-83-P, Software Engineering Research Center - Purdue University, December 1990.
• 17: W. E. Howden. Weak mutation testing and completeness of test sets. IEEE Transactions on Software Engineering, 8(4):371--379, July 1982.
• 18: G. Hughes and T. Bultan. Automated verification of access control policies. Technical Report 2004-22, Department of Computer Science, University of California, Santa Barbara, 2004.
• 19: D. S. Johnson. Approximation algorithms for combinatorial problems. J. Comput. System Sci., 9:256--278, 1974.
• 20: Edward W. Krauser , Aditya P. Mathur , Vernon J. Rego, High Performance Software Testing on SIMD Machines, IEEE Transactions on Software Engineering, v.17 n.5, p.403-423, May 1991 [doi>10.1109/32.90444]
• 21: Yu-Seung Ma , Yong-Rae Kwon , Jeff Offutt, Inter-Class Mutation Operators for Java, Proceedings of the 13th International Symposium on Software Reliability Engineering (ISSRE'02), p.352, November 12-15, 2002
• 22: Brian Marick, The weak mutation hypothesis, Proceedings of the symposium on Testing, analysis, and verification, p.190-199, October 08-10, 1991, Victoria, British Columbia, Canada [doi>10.1145/120807.120825]
• 23: Evan Martin , Tao Xie, Inferring Access-Control Policy Properties via Machine Learning, Proceedings of the Seventh IEEE International Workshop on Policies for Distributed Systems and Networks (POLICY'06), p.235-238, June 05-07, 2006 [doi>10.1109/POLICY.2006.19]
• 24: Evan Martin , Tao Xie, Automated Test Generation for Access Control Policies via Change-Impact Analysis, Proceedings of the Third International Workshop on Software Engineering for Secure Systems, p.5, May 20-26, 2007 [doi>10.1109/SESS.2007.5]
• 25: E. Martin, T. Xie, and T. Yu. Defining and measuring policy coverage in testing access control policies. In Proc. 8th International Conference on Information and Communications Security, pages 139--158, December 2006.
• 26: A. P. Mathur and E. W. Krauser. Mutant unification for improved vectorization. Technical Report SERC-TR-14-P, Software Engineering Research Center - Purdue University, 1988.
• 27: L. J. Morell, A Theory of Fault-Based Testing, IEEE Transactions on Software Engineering, v.16 n.8, p.844-857, August 1990 [doi>10.1109/32.57623]
• 28: A. Jefferson Offutt , Gregg Rothermel , Christian Zapf, An experimental evaluation of selective mutation, Proceedings of the 15th international conference on Software Engineering, p.100-107, May 17-21, 1993, Baltimore, Maryland, United States
• 29: A. Jefferson Offutt , Ammei Lee , Gregg Rothermel , Roland H. Untch , Christian Zapf, An experimental determination of sufficient mutant operators, ACM Transactions on Software Engineering and Methodology (TOSEM), v.5 n.2, p.99-118, April 1996 [doi>10.1145/227607.227610]
• 30: A. Jefferson Offutt , Stephen D. Lee, How strong is weak mutation?, Proceedings of the symposium on Testing, analysis, and verification, p.200-213, October 08-10, 1991, Victoria, British Columbia, Canada [doi>10.1145/120807.120826]
• 31: A. J. Offutt, R. Pargas, S. V. Fichter, and P. Khambekar. Mutation testing of software using a MIMD computer. In Proc. International Conference on Parallel Processing, pages 257--266, 1992.
• 32: A. J. Offutt , S. D. Lee, An Empirical Evaluation of Weak Mutation, IEEE Transactions on Software Engineering, v.20 n.5, p.337-344, May 1994 [doi>10.1109/32.286422]
• 33: J. Offutt and R. H. Untch. Mutation 2000: Uniting the orthogonal. In Mutation 2000: Mutation Testing in the Twentieth and the Twenty First Centuries, pages 45--55, October 2000.
• 34: M. Sahinoglu and E. H. Spafford. A bayes sequential statistical procedure for approving software products. In Proc. IFIP Conference on Approving Software Products, pages 43--56, 1990.
• 35: Weichen Eric Wong, On mutation and data flow, Purdue University, West Lafayette, IN, 1993
• 36: W. E. Wong, M. E. Delamaro, J. Maldonado, and A. P. Mathur. Constrained mutation in c programs. In Proc. 8th Brazilian Symposium on Software Engineering, pages 439--452, October 1994.
• 37: M. R. Woodward and K. Halewood. From weak to strong, dead or alive? an analysis of some mutation testing issues. In Proc. 2nd Workshop on Software Testing, Verification, and Analysis, pages 152--158, 1988.
• 38: Nan Zhang , Mark Ryan , Dimitar P. Guelev, Synthesising verified access control systems in XACML, Proceedings of the 2004 ACM workshop on Formal methods in security engineering, October 29-29, 2004, Washington DC, USA [doi>10.1145/1029133.1029141]
• 39: N. Zhang, M. Ryan, and D. P. Guelev. Evaluating access control policies through model checking. In Proc. 8th International Conference on Information Security, pages 446--460, September 2005.
• 40: Hong Zhu , Patrick A. V. Hall , John H. R. May, Software unit test coverage and adequacy, ACM Computing Surveys (CSUR), v.29 n.4, p.366-427, Dec. 1997 [doi>10.1145/267580.267590]

INDEX TERMS

Primary Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.5 Testing and Debugging
          Subjects: Testing tools (e.g., data generators, coverage testing)

General Terms:
Reliability

Keywords:
access control policies, fault model, mutation testing, test generation