AntiCheetah: Trustworthy computing in an outsourced (cheating) environmentby Roberto Di Pietro, Flavio Lombardi, Fabio Martinelli, Daniele Sgandurra

Future Generation Computer Systems


Computer Networks and Communications / Hardware and Architecture / Software


Roberto Di Pietro a, Flavio Lombardi b, Fabio Martinelli c, Daniele Sgandurra d,∗ a Cybersecurity Research Department, Bell Labs, Paris, France b Istituto Per le Applicazioni del Calcolo ‘‘Mauro Picone’’ (IAC) – National Research Council of Italy, Rome, Italy c Institute for Informatics and Telematics (IIT), National Research Council of Italy, Pisa, Italy d Department of Computing, Imperial College London, United Kingdom h i g h l i g h t s • We discuss an approach to enforce trustworthy computing on cheating environments. • We provide a model for autonomic, multi-round, distributed cloud computations. • The approach optimizes cost while detecting cheaters within a confidence threshold. • We evaluate the approach through extensive simulations. a r t i c l e i n f o

Article history:

Received 18 September 2014

Received in revised form 14 January 2015

Accepted 10 February 2015

Available online 18 February 2015


Trustworthy computation in cloud

Cheaters detection

Autonomous cloud computing a b s t r a c t

The increasing need for performing expensive computations has motivated outsourced computing, as in crowdsourced applications leveraging worker cloud nodes. However, these outsourced computing nodes can potentially misbehave or fail. Exploiting the redundancy of nodes can help guaranteeing correctness and availability of results. This entails that reliable distributed computing can be achieved at the expense of convenience.

In this paper, we provide a solution for a generic class of problems that distribute a parallel computation over a set of nodes where trustworthiness of the outsourced computation is important. In particular, we discuss AntiCheetah, an approach modeling the assignment of input elements to cloud nodes as a multi-round system. AntiCheetah is resilient to node cheating, even in scenarios where smart cheaters return the same fake values. To this end, cost-efficient redundancy is used to detect and correct anomalies. Furthermore, we discuss the benefits and pitfalls of the proposed approach over different scenarios, especially with respect to cheaters’ behavior. Extensive experimental results are analyzed, showing the effectiveness and viability of our approach. © 2015 Elsevier B.V. All rights reserved. 1. Introduction

In the realm of cloud computing, the term Computing-as-aService refers a formof totally-outsourced computing offered at different layers (IaaS, PaaS, SaaS) bymany alternative cloud providers (Amazon, Microsoft and Google, among the others). Software-asa-Service (SaaS), in particular, is increasingly widespread thanks ∗ Corresponding author.

E-mail addresses: (R. Di Pietro), (F. Lombardi), (F. Martinelli), (D. Sgandurra). to reduced licensing and management costs. In general High Performance Computing-as-a-Service [1,2] allows system administrators to avoid the setup and management costs due to the creation and software configuration maintenance of computing nodes.

Furthermore, the Cloud offers cheap and scalable pay-as-you-go resources where splitting and offloading computation of parallel algorithms is feasible and convenient. However, many remote computing nodes have historically been proven to misbehave, especially if they are rented with a pay-per-use approach [3]. As an example, remote computing nodes can save their energy and space resources by faking computation (i.e. pretending to compute) and returning erroneous results. One possible example is returning a random result instead of calculating a computationally-intensive function. Generation Compute

Contents lists availa

Future Generation journal homepage: www

AntiCheetah: Trustworthy computing in environment0167-739X/© 2015 Elsevier B.V. All rights reserved.r Systems 48 (2015) 28–38 ble at ScienceDirect

Computer Systems an outsourced (cheating) against smart cheaters.

Contribution of the paper. The multi-fold contribution of this paper includes: • discussing andmodeling trustworthy distributed computing on a possibly cheating environment; • detailing AntiCheetah, a multi-round approach for effectively distributing the workload over a large number of computing nodes; • evaluating AntiCheetah through extensive simulations, showing that it achieves reliable workload distribution while guaranteeing reduced cost and timeliness of results; • showing how, once the system is fed with its configuration parameters, e.g. the cost and performance of the nodes, it updates and adjusts the nodes’ parameters at each iteration, e.g. to take into account their trustworthiness, without the need of any external intervention; involved with renting cloud computing resources by keeping the timeliness of the results before a predefined threshold.

Fig. 1 shows such generic scenario, where the ISM needs to compute a function f on a vector X of length m, using a set of nodes chosen from available cloud nodes, some of which may be cheaters [5]. The output is itself a vector of length m where the jth element is f (j). The ISM would be interested to know what is the amount of cloud resources required to satisfy the above requirements, i.e. correctness and cost-efficiencywith amaximum time (Tmax) to receive the results. X has to be sent to n cloud nodes (VMs), where each node VM i has an associated unitary cost per operation ci and the time to perform an unitary operation is ti.1

Given that we assume some of the nodes are cheaters, where the percentage of cheaters (CheaterRate) is kn , where k is the numberR. Di Pietro et al. / Future Generation

Fig. 1. Use case: Node N3

In all these cases, tenants would like to have some guarantees that service level agreements (SLAs) regarding reliability are met.

The problem of secure and reliable outsourced computation is not novel, especially as regards the correctness and the timeliness of returned results. The novelty of the problem, when contextualized in the in cloud scenario, is that it is now economically feasible for tenants to dynamically rent a large number of computing resources (possibly from heterogeneous sources) at the same time.