Security and Trust in Distributed Computation

We propose three research problems to explore the relations between trust and security in the setting of distributed computation. In the first problem, we study trust-based adversary detection in distributed consensus computation. The adversaries we consider behave arbitrarily disobeying the consensus protocol. We propose a trust-based consensus algorithm with local and global trust evaluations. The algorithm can be abstracted using a two-layer structure with the top layer running a trust-based consensus algorithm and the bottom layer as a subroutine executing a global trust update scheme. We utilize a set of pre-trusted nodes, headers, to propagate local trust opinions throughout the network. This two-layer framework is flexible in that it can be easily extensible to contain more complicated decision rules, and global trust schemes. The first problem assumes that normal nodes are homogeneous, i.e. it is guaranteed that a normal node always behaves as it is programmed. In the second and third problems however, we assume that nodes are heterogeneous, i.e, given a task, the probability that a node generates a correct answer varies from node to node. The adversaries considered in these two problems are workers from the open crowd who are either investing little efforts in the tasks assigned to them or intentionally give wrong answers to questions. In the second part of the thesis, we consider a typical crowdsourcing task that aggregates input from multiple workers as a problem in information fusion. To cope with the issue of noisy and sometimes malicious input from workers, trust is used to model workers' expertise. In a multi-domain knowledge learning task, however, using scalar-valued trust to model a worker's performance is not sufficient to reflect the worker's trustworthiness in each of the domains. To address this issue, we propose a probabilistic model to jointly infer multi-dimensional trust of workers, multi-domain properties of questions, and true labels of questions. Our model is very flexible and extensible to incorporate metadata associated with questions. To show that, we further propose two extended models, one of which handles input tasks with real-valued features and the other handles tasks with text features by incorporating topic models. Our models can effectively recover trust vectors of workers, which can be very useful in task assignment adaptive to workers' trust in the future. These results can be applied for fusion of information from multiple data sources like sensors, human input, machine learning results, or a hybrid of them. In the second subproblem, we address crowdsourcing with adversaries under logical constraints. We observe that questions are often not independent in real life applications. Instead, there are logical relations between them. Similarly, workers that provide answers are not independent of each other either. Answers given by workers with similar attributes tend to be correlated. Therefore, we propose a novel unified graphical model consisting of two layers. The top layer encodes domain knowledge which allows users to express logical relations using first-order logic rules and the bottom layer encodes a traditional crowdsourcing graphical model. Our model can be seen as a generalized probabilistic soft logic framework that encodes both logical relations and probabilistic dependencies. To solve the collective inference problem efficiently, we have devised a scalable joint inference algorithm based on the alternating direction method of multipliers. The third part of the thesis considers the problem of optimal assignment under budget constraints when workers are unreliable and sometimes malicious. In a real crowdsourcing market, each answer obtained from a worker incurs cost. The cost is associated with both the level of trustworthiness of workers and the difficulty of tasks. Typically, access to expert-level (more trustworthy) workers is more expensive than to average crowd and completion of a challenging task is more costly than a click-away question. In this problem, we address the problem of optimal assignment of heterogeneous tasks to workers of varying trust levels with budget constraints. Specifically, we design a trust-aware task allocation algorithm that takes as inputs the estimated trust of workers and pre-set budget, and outputs the optimal assignment of tasks to workers. We derive the bound of total error probability that relates to budget, trustworthiness of crowds, and costs of obtaining labels from crowds naturally. Higher budget, more trustworthy crowds, and less costly jobs result in a lower theoretical bound. Our allocation scheme does not depend on the specific design of the trust evaluation component. Therefore, it can be combined with generic trust evaluation algorithms.

Move, for string quartet, piano, percussion and electronics

MOVE is a composition for string quartet, piano, percussion and electronics of approximately 15-16 minutes duration in three movements. The work incorporates electronic samples either synthesized electronically by the composer or recorded from acoustic instruments. The work aims to use electronic sounds as an expansion of the tonal palette of the chamber group (rather like an extended percussion setup) as opposed to a dominating sonic feature of the music. This is done by limiting the use of electronics to specific sections of the work, and by prioritizing blend and sonic coherence in the synthesized samples. The work uses fixed electronics in such a way that allows for tempo variations in the music. Generally, a difficulty arises in that fixed “tape” parts don’t allow tempo variations; while truly “live” software algorithms sacrifice rhythmic accuracy. Sample pads, such as the Roland SPD-SX, provide an elegant solution. The latency of such a device is close enough to zero that individual samples can be triggered in real time at a range of tempi. The percussion setup in this work (vibraphone and sample pad) allows one player to cover both parts, eliminating the need for an external musician to trigger the electronics. Compositionally, momentum is used as a constructing principle. The first movement makes prominent use of ostinato and shifting meter. The second is a set of variations on a repeated harmonic pattern, with a polymetric middle section. The third is a type of passacaglia, wherein the bassline is not introduced right away, but becomes more significant later in the movement. Given the importance of visual presentation in the Internet age, the final goal of the project was to shoot HD video of a studio performance of the work for publication online. The composer recorded audio and video in two separate sessions and edited the production using Logic X and Adobe Premiere Pro. The final video presentation can be seen at geoffsheil.com/move.

Connecting the dots: Examining the role of parental beliefs and preschoolers’ affect and engagement in predicting parent-child number exploration during a meaningful math experience

The current study examined the frequency and quality of how 3- to 4-year-old children and their parents explore the relations between symbolic and non-symbolic quantities in the context of a playful math experience, as well as the role of both parent and child factors in this exploration. Preschool children’s numerical knowledge was assessed while parents completed a survey about the number-related experiences they share with their children at home, and their math-related beliefs. Parent-child dyads were then videotaped playing a modified version of the card game War. Results suggest that parents and children explored quantity explicitly on only half of the cards and card pairs played, and dyads of young children and those with lower number knowledge tended to be most explicit in their quantity exploration. Dyads with older children, on the other hand, often completed their turns without discussing the numbers at all, likely because they were knowledgeable enough about numbers that they could move through the game with ease. However, when dyads did explore the quantities explicitly, they focused on identifying numbers symbolically, used non-symbolic card information interchangeably with symbolic information to make the quantity comparison judgments, and in some instances, emphasized the connection between the symbolic and non-symbolic number representations on the cards. Parents reported that math experiences such as card game play and quantity comparison occurred relatively infrequently at home compared to activities geared towards more foundational practice of number, such as counting out loud and naming numbers. However, parental beliefs were important in predicting both the frequency of at-home math engagement as well as the quality of these experiences. In particular, parents’ specific beliefs about their children’s abilities and interests were associated with the frequency of home math activities, while parents’ math-related ability beliefs and values along with children’s engagement in the card game were associated with the quality of dyads’ number exploration during the card game. Taken together, these findings suggest that card games can be an engaging context for parent-preschooler exploration of numbers in multiple representations, and suggests that parents’ beliefs and children’s level of engagement are important predictors of this exploration.

Security through Obscurity: Layout Obfuscation of Digital Integrated Circuits using Don't Care Conditions

Contemporary integrated circuits are designed and manufactured in a globalized environment leading to concerns of piracy, overproduction and counterfeiting. One class of techniques to combat these threats is circuit obfuscation which seeks to modify the gate-level (or structural) description of a circuit without affecting its functionality in order to increase the complexity and cost of reverse engineering. Most of the existing circuit obfuscation methods are based on the insertion of additional logic (called “key gates”) or camouflaging existing gates in order to make it difficult for a malicious user to get the complete layout information without extensive computations to determine key-gate values. However, when the netlist or the circuit layout, although camouflaged, is available to the attacker, he/she can use advanced logic analysis and circuit simulation tools and Boolean SAT solvers to reveal the unknown gate-level information without exhaustively trying all the input vectors, thus bringing down the complexity of reverse engineering. To counter this problem, some ‘provably secure’ logic encryption algorithms that emphasize methodical selection of camouflaged gates have been proposed previously in literature [1,2,3]. The contribution of this paper is the creation and simulation of a new layout obfuscation method that uses don't care conditions. We also present proof-of-concept of a new functional or logic obfuscation technique that not only conceals, but modifies the circuit functionality in addition to the gate-level description, and can be implemented automatically during the design process. Our layout obfuscation technique utilizes don’t care conditions (namely, Observability and Satisfiability Don’t Cares) inherent in the circuit to camouflage selected gates and modify sub-circuit functionality while meeting the overall circuit specification. Here, camouflaging or obfuscating a gate means replacing the candidate gate by a 4X1 Multiplexer which can be configured to perform all possible 2-input/ 1-output functions as proposed by Bao et al. [4]. It is important to emphasize that our approach not only obfuscates but alters sub-circuit level functionality in an attempt to make IP piracy difficult. The choice of gates to obfuscate determines the effort required to reverse engineer or brute force the design. As such, we propose a method of camouflaged gate selection based on the intersection of output logic cones. By choosing these candidate gates methodically, the complexity of reverse engineering can be made exponential, thus making it computationally very expensive to determine the true circuit functionality. We propose several heuristic algorithms to maximize the RE complexity based on don’t care based obfuscation and methodical gate selection. Thus, the goal of protecting the design IP from malicious end-users is achieved. It also makes it significantly harder for rogue elements in the supply chain to use, copy or replicate the same design with a different logic. We analyze the reverse engineering complexity by applying our obfuscation algorithm on ISCAS-85 benchmarks. Our experimental results indicate that significant reverse engineering complexity can be achieved at minimal design overhead (average area overhead for the proposed layout obfuscation methods is 5.51% and average delay overhead is about 7.732%). We discuss the strengths and limitations of our approach and suggest directions that may lead to improved logic encryption algorithms in the future. References: [1] R. Chakraborty and S. Bhunia, “HARPOON: An Obfuscation-Based SoC Design Methodology for Hardware Protection,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 28, no. 10, pp. 1493–1502, 2009. [2] J. A. Roy, F. Koushanfar, and I. L. Markov, “EPIC: Ending Piracy of Integrated Circuits,” in 2008 Design, Automation and Test in Europe, 2008, pp. 1069–1074. [3] J. Rajendran, M. Sam, O. Sinanoglu, and R. Karri, “Security Analysis of Integrated Circuit Camouflaging,” ACM Conference on Computer Communications and Security, 2013. [4] Bao Liu, Wang, B., "Embedded reconfigurable logic for ASIC design obfuscation against supply chain attacks,"Design, Automation and Test in Europe Conference and Exhibition (DATE), 2014 , vol., no., pp.1,6, 24-28 March 2014.