The Efficient Server Audit Problem, Deduplicated Re-execution, and the Web

Posted ON November 07, 2017

Authors: Joshua Leners (Two Sigma), Cheng Tan, Lingfan Yu, Michael Walfish

Published in: Proceedings of the 26th Symposium on Operating Systems Principles, SOSP'17, Pages 546-564

Abstract: You put a program on a concurrent server, but you don't trust the server; later, you get a trace of the actual requests that the server received from its clients and the responses that it delivered. You separately get logs from the server; these are untrusted. How can you use the logs to efficiently verify that the responses were derived from running the program on the requests? This is the Efficient Server Audit Problem, which abstracts real-world scenarios, including running a web application on an untrusted provider. We give a solution based on several new techniques, including simultaneous replay and efficient verification of concurrent executions. We implement the solution for PHP web applications. For several applications, our verifier achieves 5.6-10.9x speedup versus simply re-executing, with <10% overhead for the server.

DOIhttps://doi.org/10.1145/3132747.3132760

Related Articles

Life at Two Sigma

We’re rigorous about our work and developing our people.

Learn More

Interested in working at Two Sigma? Explore careers.

This website uses cookies to ensure you get the best experience on our website. Learn More
Got It