TESSERACT’s evaluation framework and its use of MaMaDroid

In this blog post, we will describe and comment on TESSERACT, a system introduced in a paper to appear at USENIX Security 2019, and previously published as a pre-print. TESSERACT is a publicly available framework for the evaluation and comparison of systems based on statistical classifiers, with a particular focus on Android malware classification. The authors used DREBIN and our MaMaDroid paper as examples of this evaluation. Their choice is because these are two of the most important state-of-the-art papers, tackling the challenge from different angles, using different models, and different machine learning algorithms. Moreover, DREBIN has already been reproduced by researchers even though the code is not available anymore; MaMaDroid’s code is publicly available (the parsed data and the list of samples are available under request). I am one of MaMaDroid’s authors, and I am particularly interested in projects like TESSERACT. Therefore, I will go through this interesting framework and attempt to clarify a few misinterpretations made by the authors about MaMaDroid.

The need for evaluation frameworks

The information security community and, in particular, the systems part of it, feels that papers are often rejected based on questionable decisions or, on the other hand, that papers should be more rigorous, trying to respect certain important characteristics. Researchers from Dutch universities published a survey of papers published to top venues in 2010 and 2015 where they evaluated if these works were presenting “crimes” affecting completeness, relevancy, soundness, and reproducibility of the work. They have shown how the newest publications present more flaws. Even though the authors included their works in the analyzed ones and did not word the paper as a wall of shame by pointing the finger against specific articles, the paper has been seen as an attack to the community rather than an incitement to produce more complete papers. To the best of my knowledge, unfortunately, the paper has not yet been accepted for publication. TESSERACT is another example of researchers’ effort in trying to make the community work more rigorous: most system papers present accuracies that are close to 100% in all the tests done; however, when some of them have been tested on different datasets, their accuracy was worse than a coin toss.

These two works are part of a trend that I personally find important for our community, to allow works that are following other ones on the chronological aspects to be evaluated in a more fair way. I explain with a personal example: I recall when my supervisor told me that at the beginning he was not optimistic about MaMaDroid being accepted at the first attempt (NDSS 2017) because most of the previous literature shows results always over 98% accuracy and that gap of a few percentage points can be enough for some reviewers to reject. When we asked an opinion of a colleague about the paper, before we submitted it for peer-review, this was his comment on the ML part: “I actually think the ML part is super solid, and I’ve never seen a paper with so many experiments on this topic.” We can see completely different reactions over the same specific part of the work.

TESSERACT

The goal of this post is to show TESSERACT’s potential while pointing out the small misinterpretations of MaMaDroid present in the current version of the paper. The authors contacted us to let us read the paper and see whether there has been any misinterpretation. I had a constructive meeting with the authors where we also had the opportunity to exchange opinions on the work. Following the TESSERACT description, there will be a section related to MaMaDroid’s misinterpretations in the paper. The authors told me that the newest versions would be updated according to what we discussed.

Continue reading TESSERACT’s evaluation framework and its use of MaMaDroid

Introducing Sonic: A Practical zk-SNARK with a Nearly Trustless Setup

In this post, we discuss a new zk-SNARK, Sonic, developed by Mary Maller, Sean Bowe, Markulf Kohlweiss and Sarah Meiklejohn. Unlike other SNARKs, Sonic does not require a trusted setup for each circuit, but only a single setup for all circuits. Further, the setup for Sonic never has to end, so it can be continuously secured by accumulating more contributions. This property makes it ideal for any system where there is not a trusted party, and there is a need to validate data without leaking confidential information. For example, a company might wish to show solvency to an auditor without revealing which products they have invested in. The construction is highly practical.

More about zk-SNARKs

Like all other zero-knowledge proofs, zk-SNARKs are a tool used to build applications where users must prove the validity of their data, such as in verifiable computation or anonymous credentials. Additionally, zk-SNARKs have the smallest proof sizes and verifier time out of all other known techniques for building zero-knowledge proofs. However, they typically require a trusted setup process, introducing the possibility of fraudulent data being input by the actors that implemented the system. For example, Zcash uses zk-SNARKs to send private cryptocurrency transactions, and if their setup was compromised then a small number of users could generate an unlimited supply of currency without detection.

Characteristics of zk-SNARKs
🙂 Can be used to build many cryptographic protocols
🙂 Very small proof sizes
🙂 Very fast verifier time
😐 Average prover time
☹️ Requires a trusted setup
☹️ Security assumes non-standard cryptographic assumptions

In 2018, Groth et al. introduced a zk-SNARK that could be built from an updatable and universal setup. We describe these properties below and claim that these properties help mitigate the security concerns around trusted setup. However, unlike Sonic, Groth et al.’s setup outputs a large set of global parameters (in the order of terabytes), which would be unwieldy to store, update and verify.

Updatability

Updatability means that any user, at any time, can update the parameters, including after the system goes live. After a single honest user has participated, no party can prove fraudulent data. This property means that a distrustful user could update the parameters themselves and have personal confidence in the parameters from that point forward. The update proofs are short and quick to verify.

Universality

Universality means that the same parameters can be used for any application using this zk-SNARK. Thus one can imagine including the global parameters in an open-source implementation, or one could use the same parameters for all smart contracts in Ethereum.

Why Use Sonic?

Sonic is universal, updatable, and has a small set of global parameters (in the order of megabytes). Proof sizes are small (256 bytes) and verifier time is competitive with the fastest zk-SNARKs in the literature. It is especially well suited to systems where the same zk-SNARK is run by many different provers and verified by many different parties. This is exactly the situation for many blockchain systems.

Continue reading Introducing Sonic: A Practical zk-SNARK with a Nearly Trustless Setup