Hardware counter driven on-the-fly request signatures

ABSTRACT

Today's processors provide a rich source of statistical informationon application execution through hardware counters. In this paper, we explore the utilization of these statistics as request signaturesin server applications for identifying requests and inferring high-level request properties (e.g., CPU and I/O resource needs). Our key finding is that effective request signatures may be constructed using a small amount of hardware statistics while the request is still in an early stage of its execution. Such on-the-fly request identification and property inference allow guided operating system adaptation at request granularity (e.g., resource-aware request scheduling and on-the-fly request classification). We address the challenges of selecting hardware counter metrics for signature construction and providing necessary operating system support for per-request statistics management. Our implementation in the Linux 2.6.10 kernel suggests that our approach requires low overhead suitable for runtime deployment. Our on-the-fly request resource consumption inference (averaging 7%, 3%, 20%, and 41% prediction errors for four server workloads, TPC-C, TPC-H, J2EE-based RUBiS, and a trace-driven index search, respectively) is much more accurate than the online running-average based prediction (73-82% errors). Its use for resource-aware request scheduling results in a 15-70% response time reduction for three CPU-bound applications. Its use for on-the-fly request classification and anomaly detection exhibits high accuracy for the TPC-H workload with synthetically generated anomalous requests following a typical SQL-injection attack pattern.

REFERENCES

• 1: Marcos K. Aguilera , Jeffrey C. Mogul , Janet L. Wiener , Patrick Reynolds , Athicha Muthitacharoen, Performance debugging for distributed systems of black boxes, Proceedings of the nineteenth ACM symposium on Operating systems principles, October 19-22, 2003, Bolton Landing, NY, USA
• 2: Jennifer M. Anderson , Lance M. Berc , Jeffrey Dean , Sanjay Ghemawat , Monika R. Henzinger , Shun-Tak A. Leung , Richard L. Sites , Mark T. Vandevoorde , Carl A. Waldspurger , William E. Weihl, Continuous profiling: where have all the cycles gone?, ACM Transactions on Computer Systems (TOCS), v.15 n.4, p.357-390, Nov. 1997 [doi>10.1145/265924.265925]
• 3: C. Anley. Advanced SQL Injection in SQL Server Applications. Technical report, Next Generation Security Software Ltd., 2002.
• 4: Ask.com Search Engine (formerly Ask Jeeves). http://www.ask.com.
• 5: Reza Azimi , Michael Stumm , Robert W. Wisniewski, Online performance analysis by statistical sampling of microprocessor performance counters, Proceedings of the 19th annual international conference on Supercomputing, June 20-22, 2005, Cambridge, Massachusetts [doi>10.1145/1088149.1088163]
• 6: Gaurav Banga , Peter Druschel , Jeffrey C. Mogul, Resource containers: a new facility for resource management in server systems, Proceedings of the third symposium on Operating systems design and implementation, p.45-58, February 1999, New Orleans, Louisiana, United States
• 7: Nikhil Bansal , Mor Harchol-Balter, Analysis of SRPT scheduling: investigating unfairness, Proceedings of the 2001 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, p.279-290, June 2001, Cambridge, Massachusetts, United States
• 8: Paul Barham , Austin Donnelly , Rebecca Isaacs , Richard Mortier, Using magpie for request extraction and workload modelling, Proceedings of the 6th conference on Symposium on Opearting Systems Design & Implementation, p.18-18, December 06-08, 2004, San Francisco, CA
• 9: Josep M. Blanquer , Antoni Batchelli , Klaus Schauser , Rich Wolski, Quorum: flexible quality of service for internet services, Proceedings of the 2nd conference on Symposium on Networked Systems Design & Implementation, p.159-174, May 02-04, 2005
• 10: James R. Bulpin , Ian A. Pratt, Hyper-threading aware process scheduling heuristics, Proceedings of the annual conference on USENIX Annual Technical Conference, p.27-27, April 10-15, 2005, Anaheim, CA
• 11: Jeffrey S. Chase , Darrell C. Anderson , Prachi N. Thakar , Amin M. Vahdat , Ronald P. Doyle, Managing energy and server resources in hosting centers, Proceedings of the eighteenth ACM symposium on Operating systems principles, October 21-24, 2001, Banff, Alberta, Canada
• 12: Mike Y. Chen , Anthony Accardi , Emre Kiciman , Jim Lloyd , Dave Patterson , Armando Fox , Eric Brewer, Path-based faliure and evolution management, Proceedings of the 1st conference on Symposium on Networked Systems Design and Implementation, p.23-23, March 29-31, 2004, San Francisco, California
• 13: Ira Cohen , Steve Zhang , Moises Goldszmidt , Julie Symons , Terence Kelly , Armando Fox, Capturing, indexing, clustering, and retrieving system history, Proceedings of the twentieth ACM symposium on Operating systems principles, October 23-26, 2005, Brighton, United Kingdom
• 14: Ashutosh S. Dhodapkar , James E. Smith, Managing multi-configuration hardware via dynamic working set analysis, Proceedings of the 29th annual international symposium on Computer architecture, May 25-29, 2002, Anchorage, Alaska
• 15: Evelyn Duesterwald , Calin Cascaval , Sandhya Dwarkadas, Characterizing and Predicting Program Behavior and its Variability, Proceedings of the 12th International Conference on Parallel Architectures and Compilation Techniques, p.220, September 27-October 01, 2003
• 16: Lieven Eeckhout , Hans Vandierendonck , Koenraad De Bosschere, Workload Design: Selecting Representative Program-Input Pairs, Proceedings of the 2002 International Conference on Parallel Architectures and Compilation Techniques, p.83-94, September 22-25, 2002
• 17: Chris Gniady , Ali R. Butt , Y. Charlie Hu, Program-counter-based pattern classification in buffer caching, Proceedings of the 6th conference on Symposium on Opearting Systems Design & Implementation, p.27-27, December 06-08, 2004, San Francisco, CA
• 18: W.G.J. Halfond, J. Viegas, and A. Orso. A Classification of SQL Injection Attacks and Countermeasures. In Int'l Symp. on Secure Software Engineering, Arlington, VA, March 2006.
• 19: Mor Harchol-Balter , Bianca Schroeder , Nikhil Bansal , Mukesh Agrawal, Size-based scheduling to improve web performance, ACM Transactions on Computer Systems (TOCS), v.21 n.2, p.207-233, May 2003 [doi>10.1145/762483.762486]
• 20: RUBiS: Rice University Bidding System. http://rubis.objectweb.org.
• 21: L.E. Schrage and L.W. Miller. The Queue M/G/1 with the Shortest Remaining Processing Time Discipline. Operations Research, 14(4):670--684, 1966.
• 22: Kai Shen , Hong Tang , Tao Yang , Lingkun Chu, Integrated resource management for cluster-based internet services, Proceedings of the 5th symposium on Operating systems design and implementation

  Due to copyright restrictions we are not able to make the PDFs for this conference available for downloading

  , December 09-11, 2002, Boston, Massachusetts [doi>10.1145/1060289.1060311]
• 23: Timothy Sherwood , Suleyman Sair , Brad Calder, Phase tracking and prediction, Proceedings of the 30th annual international symposium on Computer architecture, June 09-11, 2003, San Diego, California
• 24: Christopher Stewart , Kai Shen, Performance modeling and system management for multi-component online services, Proceedings of the 2nd conference on Symposium on Networked Systems Design & Implementation, p.71-84, May 02-04, 2005
• 25: Peter F. Sweeney , Matthias Hauswirth , Brendon Cahoon , Perry Cheng , Amer Diwan , David Grove , Michael Hind, Using hardware performance monitors to understand the behavior of java applications, Proceedings of the 3rd conference on Virtual Machine Research And Technology Symposium, p.5-5, May 06-07, 2004, San Jose, California
• 26: TPC Benchmark C. http://www.tpc.org/tpcc.
• 27: TPC Benchmark H. http://www.tpc.org/tpch.
• 28: Rob von Behren , Jeremy Condit , Feng Zhou , George C. Necula , Eric Brewer, Capriccio: scalable threads for internet services, Proceedings of the nineteenth ACM symposium on Operating systems principles, October 19-22, 2003, Bolton Landing, NY, USA
• 29: Xiao Zhang , Sandhya Dwarkadas , Girts Folkmanis , Kai Shen, Processor hardware counter statistics as a first-class system resource, Proceedings of the 11th USENIX workshop on Hot topics in operating systems, p.1-6, May 07-09, 2007, San Diego, CA

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.7 Organization and Design

General Terms:
Design, Experimentation, Measurement, Performance, Reliability

Keywords:
anomaly detection, hardware counter, operating system adaptation, request classification, server system