skip to main content
10.1145/2524224.2524233acmconferencesArticle/Chapter ViewAbstractPublication PagessospConference Proceedingsconference-collections
research-article

Towards privacy-preserving fault detection

Published: 03 November 2013 Publication History

Abstract

In this paper, we discuss the problem of detecting general faults in distributed systems that handle confidential information. Detecting non-crash faults is difficult in this setting because, to check the behavior of a given node, we need to know its expected behavior -- but that can depend on the confidential information. Classical zero-knowledge proofs are difficult to apply because they are designed to verify functions with a fixed number of inputs, but in many distributed systems, both the size and the number of a node's "inputs" (the messages it has received from other nodes) are not known.
We propose an approach that can efficiently provide zero-knowledge fault detection for certain systems. Our approach spreads the detection tasks across multiple nodes, leveraging a node's existing knowledge whenever possible. We use epistemic reasoning to infer such knowledge, and we combine classical zero-knowledge proofs with a special data structure to handle inputs of unknown size. We show how our approach can be applied to a simple example system, and we report some initial performance measurements.

References

[1]
R. Agrawal and R. Srikant. Privacy-preserving data mining. In Proc. SIGMOD, 2000.
[2]
S. Angel and M. Walfish. Verifiable auctions for online ad exchanges. In Proc. SIGCOMM, Aug. 2013.
[3]
M. Backes, M. Maffei, and K. Pecina. Automated synthesis of privacy-preserving distributed applications. In NDSS, 2012.
[4]
K. M. Chandy and L. Lamport. Distributed snapshots: determining global states of distributed systems. ACM Trans. Comput. Syst., 3(1): 63--75, Feb. 1985.
[5]
S. Davidson, S. Khanna, S. Roy, J. Stoyanovich, V. Tannen, and Y. Chen. On provenance and privacy. In ICDT, 2011.
[6]
Y. Duan, J. Canny, and J. Zhan. P4P: practical large-scale privacy-preserving distributed computation robust against malicious users. In Proc. USENIX Security, 2010.
[7]
Y. Duan and J. F. Canny. Practical private computation and zero-knowledge tools for privacy-preserving distributed data mining. In Proc. SDM, 2008.
[8]
R. Fagin, M. Naor, and P. Winkler. Comparing information without leaking it. Commun. ACM, 39(5): 77--85, 1996.
[9]
R. Gennaro, C. Gentry, B. Parno, and M. Raykova. Quadratic span programs and succinct NIZKs without PCPs. In Proc. EUROCRYPT, 2013.
[10]
S. Goldwasser, S. Micali, and C. Rackoff. The knowledge complexity of interactive proof-systems. In STOC, 1985.
[11]
J. Groth. Short pairing-based non-interactive zero-knowledge arguments. In Proc. ASIACRYPT, 2010.
[12]
A. J. T. Gurney, A. Haeberlen, W. Zhou, M. Sherr, and B. T. Loo. Having your cake and eating it too: Routing security with privacy protections. In Proc. HotNets, Nov. 2011.
[13]
A. Haeberlen, P. Aditya, R. Rodrigues, and P. Druschel. Accountable virtual machines. In Proc. OSDI, Oct. 2010.
[14]
A. Haeberlen, I. Avramopoulos, J. Rexford, and P. Druschel. NetReview: Detecting when interdomain routing goes wrong. In Proc. NSDI, Apr 2009.
[15]
A. Haeberlen and P. Kuznetsov. The Fault Detection Problem. In Proc. OPODIS, Dec. 2009.
[16]
A. Haeberlen, P. Kuznetsov, and P. Druschel. PeerReview: Practical accountability for distributed systems. In Proc. SOSP, Oct 2007.
[17]
A. Haeberlen, M. Zhao, W. Zhou, A. J. T. Gurney, M. Sherr, and B. T. Loo. Privacy-preserving collaborative verification protocols. In Proc. LADIS, 2012.
[18]
J. Y. Halpern and Y. Moses. Knowledge and common knowledge in a distributed environment. J. ACM, 37(3): 549--587, July 1990.
[19]
L. Lamport, R. Shostak, and M. Pease. The Byzantine generals problem. ACM TOPLAS, 4(3): 382--401, 1982.
[20]
Y. Lindell and B. Pinkas. Privacy preserving data mining. In Proc. CRYPTO, 2000.
[21]
H. Lipmaa. Verifiable homomorphic oblivious transfer and private equality test. In Proc. ASIACRYPT, 2003.
[22]
B. Loo, T. Condie, M. Garofalakis, D. Gay, J. M. Hellerstein, P. Maniatis, R. Ramakrishnan, T. Roscoe, and I. Stoica. Declarative networking. CACM, 52(11): 87--95, Nov. 2009.
[23]
R. Merkle. Protocols for public key cryptosystems. In Proc. Symposium on Security and Privacy, Apr. 1980.
[24]
S. Micali, M. Rabin, and J. Kilian. Zero-knowledge sets. In Proc. FOCS, Oct. 2003.
[25]
B. Parno, C. Gentry, J. Howell, and M. Raykova. Pinocchio: Nearly practical verifiable computation. In Proc. IEEE Symposium on Security and Privacy, May 2013.
[26]
S. Setty, B. Braun, V. Vu, A. J. Blumberg, B. Parno, and M. Walfish. Resolving the conflict between generality and plausibility in verified computation. In Proc. EuroSys, 2013.
[27]
S. Setty, R. McPherson, A. J. Blumberg, and M. Walfish. Making argument systems for outsourced computation practical (sometimes). In Proc. NDSS, Feb. 2012.
[28]
S. Setty, V. Vu, N. Panpalia, B. Braun, A. J. Blumberg, and M. Walfish. Taking proof-based verified computation a few steps closer to practicality. In Proc. USENIX Security, 2012.
[29]
V. Vu, S. Setty, A. J. Blumberg, and M. Walfish. A hybrid architecture for interactive verifiable computation. In Proc. IEEE Symposium on Security and Privacy, May 2013.
[30]
A. C. Yao. Protocols for secure computations. In Proc. Symposium on Foundations of Computer Science (SFCS), 1982.
[31]
M. Zhao, W. Zhou, A. J. T. Gurney, A. Haeberlen, M. Sherr, and B. T. Loo. Private and verifiable interdomain routing decisions. In Proc. SIGCOMM, 2012.

Cited By

View all

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences
HotDep '13: Proceedings of the 9th Workshop on Hot Topics in Dependable Systems
November 2013
64 pages
ISBN:9781450324571
DOI:10.1145/2524224
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 03 November 2013

Permissions

Request permissions for this article.

Check for updates

Qualifiers

  • Research-article

Funding Sources

Conference

SOSP '13
Sponsor:

Acceptance Rates

HotDep '13 Paper Acceptance Rate 11 of 21 submissions, 52%;
Overall Acceptance Rate 11 of 21 submissions, 52%

Upcoming Conference

SOSP '25
ACM SIGOPS 31st Symposium on Operating Systems Principles
October 13 - 16, 2025
Seoul , Republic of Korea

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)8
  • Downloads (Last 6 weeks)0
Reflects downloads up to 20 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (2019)Robust Temporal Logic Inference for Provably Correct Fault Detection and Privacy Preservation of Switched SystemsIEEE Systems Journal10.1109/JSYST.2019.290616013:3(3010-3021)Online publication date: Sep-2019
  • (2019)DAPV: Diagnosing Anomalies in MANETs Routing With Provenance and VerificationIEEE Access10.1109/ACCESS.2019.29031507(35302-35316)Online publication date: 2019
  • (2019)SRDPVWireless Networks10.1007/s11276-017-1625-825:4(1731-1747)Online publication date: 1-May-2019
  • (2017)PVad: Privacy-Preserving Verification for Secure Routing in Ad Hoc Networks2017 International Conference on Networking and Network Applications (NaNA)10.1109/NaNA.2017.21(5-10)Online publication date: Oct-2017
  • (2016)PAG: Private and Accountable Gossip2016 IEEE 36th International Conference on Distributed Computing Systems (ICDCS)10.1109/ICDCS.2016.34(35-44)Online publication date: Jun-2016
  • (2015)CRVad: Confidential Reasoning and Verification Towards Secure Routing in Ad Hoc NetworksAlgorithms and Architectures for Parallel Processing10.1007/978-3-319-27137-8_33(449-462)Online publication date: 16-Dec-2015

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media