2020
Software engineering involves writing new code or editing existing code. Recent efforts have investigated the neural processes associated with reading and comprehending code —- however, we lack a thorough understanding of the human cognitive processes underlying code writing. While prose reading and writing have been studied thoroughly, that same scrutiny has not been applied to code writing. In this paper, we leverage functional brain imaging to investigate neural representations of code writing in comparison to prose writing. We present the first human study in which participants wrote code and prose while undergoing a functional magnetic resonance imaging (fMRI) brain scan, making use of a full-sized fMRI-safe QWERTY keyboard.We find that code writing and prose writing are significantly dissimilar neural tasks. While prose writing entails significant left hemisphere activity associated with language, code writing involves more activations of the right hemisphere, including regions associated with attention control, working memory, planning and spatial cognition. These findings are unlike existing work in which code and prose comprehension were studied. By contrast, we present the first evidence suggesting that code and prose writing are quite dissimilar at the neural level.
publication
Biases and Differences in Code Review Using Medical Imaging and Eye-Tracking: Genders, Humans, and Machines
Code review is a critical step in modern software quality assurance, yet it is vulnerable to human biases. Previous studies have clarified the extent of the problem, particularly regarding biases against the authors of code,but no consensus understanding has emerged. Advances in medical imaging are increasingly applied to software engineering, supporting grounded neurobiological explorations of computing activities, including the review, reading, and writing of source code. In this paper, we present the results of a controlled experiment using both medical imaging and also eye tracking to investigate the neurological correlates of biases and differences between genders of humans and machines (e.g., automated program repair tools) in code review. We find that men and women conduct code reviews differently, in ways that are measurable and supported by behavioral, eye-tracking and medical imaging data. We also find biases in how humans review code as a function of its apparent author, when controlling for code quality. In addition to advancing our fundamental understanding of how cognitive biases relate to the code review process, the results may inform subsequent training and tool design to reduce bias.
publication
KShot: Live Kernel Patching with SMM and SGX
Live kernel patching is an increasingly common trend in operating system distributions, enabling dynamic updates to include new features or to fix vulnerabilities without having to reboot the system. Patching the kernel at runtime lowers downtime and reduces the loss of useful state from running applications. However, existing kernel live patching techniques (1) rely on specific support from the target operating system, and (2) admit patch failures resulting from kernel faults. We present KSHOT, a kernel live patching mechanism based on x86 SMM and Intel SGX that focuses on patching Linux kernel security vulnerabilities. Our patching processes are protected by hardware-assisted Trusted Execution Environments. We demonstrate that our technique can successfully patch vulnerable kernel functions at the binary-level without support from the underlying OS and regardless of whether the kernel patching mechanism is compromised. We demonstrate the applicability of KSHOT by successfully patching 30 critical indicative kernel vulnerabilities.
publication
MARTINI: Memory Access Traces to Detect Attacks
Hardware architectural vulnerabilities, such as Spectre and Meltdown, are difficult or inefficient to mitigate in software. Although revised hardware designs may address some architectural vulnerabilities going forward, most current remedies increase execution time significantly. Techniques are needed to rapidly and efficiently detect these and other emerging threats. We present an anomaly detector, MARTINI, that analyzes traces of memory accesses in real time to detect attacks. Our experimental evaluation shows that anomalies in these traces are strongly correlated with unauthorized program execution, including architectural side-channel attacks of multiple types. MARTINI consists of a finite automaton that models normal program behavior in terms of memory addresses that are read from, and written to, at runtime. The model uses a compact representation of n-grams, i.e., short sequences of memory accesses, which can be stored and processed efficiently. Once the system is trained on authorized behavior, it rapidly detects a variety of low-level anomalous behaviors and attacks not otherwise easily discernible at the software level. MARTINI s implementation leverages recent advances in in-cache and in-memory automata for computation, and we present a hardware unit that repurposes a small portion of a last-level cache slice to monitor memory addresses. Our detector directly inspects the addresses of memory accesses, using the pre-constructed automaton to identify anomalies with high accuracy, negligible runtime overhead, and trivial increase in CPU chip area. We present analyses of expected hardware properties based on indicative cache and memory hierarchy simulations and empirical evaluations.
With the proliferation of location-based services enabled by a large number of mobile devices and applications, the quantity of location data, such as trajectories collected by service providers, is gigantic. If these datasets could be published, then they would be valuable assets to various service providers to explore business opportunities, to study commuter behavior for better transport management, which in turn benefits the general public for day-to-day commuting. However, there are two major concerns that considerably limit the availability and the usage of these trajectory datasets. The first is the threat to individual privacy, as users’ trajectories may be misused to discover sensitive information, such as home locations, their children’s school locations, or social information like habits or relationships. The other concern is the ability to analyze the exabytes of location data in a timely manner. Although there have been trajectory anonymization approaches proposed in the past to mitigate privacy concerns. None of these prior works address the scalability issue, since it is a newly occurring problem brought by the significantly increasing adoption of location-based services. In this article, we conquer these two challenges by designing a novel parallel trajectory anonymization algorithm that achieves scalability, strong privacy protection, and high utility rate of the anonymized trajectory datasets. We have conducted extensive experiments using MapReduce and Spark on real maps with different topologies, and our results prove both effectiveness and efficiency when compared with the centralized approaches.
People constantly share their photographs with others through various social media sites. With the aid of the privacy settings provided by social media sites, image owners can designate scope of sharing, e.g., close friends and acquaintances. However, even if the owner of a photograph carefully sets the privacy setting to exclude a given individual who is not supposed to see the photograph, the photograph may still eventually reach a wider audience, including those clearly undesired through unanticipated channels of disclosure, causing a privacy breach. Moreover, it is often the case that a given image involves multiple stakeholders who are also depicted in the photograph. Due to various personalities, it is even more challenging to reach agreement on the privacy settings for these multi-owner photographs. In this paper, we propose a privacy risk reminder system, called REMIND, which estimates the probability that a shared photograph may be seen by unwanted people-through the social graph-who are not included in the original sharing list. We tackle this problem from a novel angle by digging into the big data regarding image sharing history. Specifically, the social media providers possess a huge amount of image sharing information (e.g., what photographs are shared with whom) of their users. By analyzing and modeling such rich information, we build a sophisticated probability model that efficiently aggregates the image disclosure probabilities along different possible image propagation chains and loops. If the computed disclosure probability indicates high risks of privacy breach, a reminder is issued to the image owner to help revise the privacy settings (or, at least, inform the user about this accidental disclosure risk). The proposed REMIND system also has a nice feature of policy harmonization that helps resolve privacy differences in multi-owner photographs. We have carried out a user study to validate the rationale of our proposed solutions and also conducted experimental studies to evaluate the efficiency of the proposed REMIND system.
With the prevalence of smartphones, mobile websites have been more and more popular. However, many mobile websites collect the location information which greatly increases users risks of being tracked unexpectedly. The current location access control setting is not sufficient since it cannot prevent the service providers which have been granted location-access permissions from tracking the users. In this paper, we propose a novel location privacy preservation mobile app, called MoveWithMe, which automatically generates decoy queries to hide the real users locations and intentions when they are using location-based mobile services. Unlike the existing works on dummy trajectories which may be easily discovered by attackers through data analysis, the uniqueness of the MoveWithMe app is that our generated decoys closely behave like real humans. Each decoy in our system has its own moving patterns, daily schedules, and social behaviors, which ensures its movements to be semantically different from the real user s trace and satisfying geographic constraints. Thus, our decoys can hardly be distinguished even by advanced data mining techniques. Another advantage of the MoveWithMe app is that it guarantees the same level of user experience without affecting the response time or introducing extra control burdens. Decoys move independently in the back end and automatically submit queries to the same service provider whenever the user does so. Our proposed MoveWithMe app has both iOS and Android versions and has been tested on different brands of smartphones against various location-based services, such as Yelp and TripAdvisor. Experimental results demonstrate its practicality, effectiveness, and efficiency.
publication
A physical hash for preventing and detecting cyber-physical attacks in additive manufacturing systems
Cyber-physical security is a major concern in the modern environment of digital manufacturing, wherein a cyber-attack has the potential to result in the production of defective parts, theft of IP, or damage to infrastructure or the operator have become a real threat that have the potential to create bad parts. Current cyber only solutions are insufficient due to the nature of manufacturing environments where it may not be feasible or even possible to upgrade physical equipment to the most current cyber security standards, necessitating an approach that addresses both the cyber and the physical components. This paper proposes a new method for detecting malicious cyber-physical attacks on additive manufacturing (AM) systems. The method makes use of a physical hash, which links digital data to the manufactured part via a disconnected side-channel measurement system. The disconnection ensures that if the network and/or AM system becomes compromised, the manufacturer can still rely on the measurement system for attack detection. The physical hash ensures protection of the intellectual property (IP) associated with both process and toolpath parameters while also enabling in situ quality assurance. In this paper, the physical hash takes the form of a QR code that contains a hash string of the nominal process parameters and toolpath. It is manufactured alongside the original geometry for the measurement system to scan and compare to the readings from its sensor suite. By taking measurements in situ, the measurement system can detect in real-time if the part being manufactured matches the designer’s specification. In this paper, the overall concept and underlying algorithm of the physical hash is presented. A proof-of-concept validation is realized on a material extrusion AM machine, to demonstrate the ability of a physical hash and in situ monitoring to detect the existence (and absence) of malicious attacks on the STL file, the printing process parameters, and the printing toolpath.
publication
Graph-Theoretic Approach for Increasing Participation in Networks With Assorted Resources
In many cooperative networks, individuals participate actively as long as they recognize a sufficient value in participation, which depends not only on the number, but also on the attributes of other participating members. In this paper, we present a generalized model of individuals participation in such networks, and a strategy to maximize the number of participating individuals. Unlike most of the existing literature, our model incorporates both the network structure and the heterogeneity of individuals in terms of their attributes and resources. We consider that each individual possesses a subset of available resources (attributes), which it shares with neighbors as long as neighbors reciprocate and provide the missing resources to the individual. However, individual leaves the network if it cannot find all the resources in its neighborhood. To model this phenomenon, we introduce a graph-theoretic notion of the (r,s)-core, which is the sub-network consisting of only those individuals who can access all the resources by collaborating with their neighbors. Since disengagement of an individual could initiate a cascading withdrawal of more individuals from the network, one of our main goals is to prevent this unraveling and maximize the number of participating individuals. For this purpose, we utilize the notion of anchors-individuals that continue to participate (due to incentives) even if they cannot find all of the resources in their neighborhood. By introducing only a few anchors, we can significantly increase the number of participating individuals, which in our model corresponds to increasing the size of the (r,s)-core. We formulate and thoroughly analyze the anchors selection problem by classifying the cases in which the problem is polynomial-time solvable, NP-complete, and inapproximable. Further, we provide greedy and metaheuristic search algorithms to compute a set of anchors and evaluate our results on various networks. Our results are applicable to a large number of cooperative networking applications, including participatory sensing in which users develop an elaborate knowledge of their environment through sharing measurements.
Distributed multi-task learning provides significant advantages in multi-agent networks with heterogeneous data sources where agents aim to learn distinct but correlated models simultaneously. However, distributed algorithms for learning relatedness among tasks are not resilient in the presence of Byzantine agents. In this paper, we present an approach for Byzantine resilient distributed multi-task learning. We propose an efficient online weight assignment rule by measuring the accumulated loss using an agent s data and its neighbors models. A small accumulated loss indicates a large similarity between the two tasks. In order to ensure the Byzantine resilience of the aggregation at a normal agent, we introduce a step for filtering out larger losses. We analyze the approach for convex models and show that normal agents converge resiliently towards the global minimum. Further, aggregation with the proposed weight assignment rule always results in an improved expected regret than the non-cooperative case. Finally, we demonstrate the approach using three case studies, including regression and classification problems, and show that our method exhibits good empirical performance for non-convex models, such as convolutional neural networks.
We study the strong structural controllability (SSC) of diffusively coupled networks, where the external control inputs are injected to only some nodes, namely the leaders. For such systems, one measure of controllability is the dimension of strong structurally controllable subspace, which is equal to the smallest possible rank of controllability matrix under admissible (positive) coupling weights. In this paper, we compare two tight lower bounds on the dimension of strong structurally controllable subspace: one based on the distances of followers to leaders, and the other based on the graph coloring process known as zero forcing. We show that the distance-based lower bound is usually better than the zero-forcing-based bound when the leaders do not constitute a zero-forcing set. On the other hand, we also show that any set of leaders that can be shown to achieve complete SSC via the distance-based bound is necessarily a zero-forcing set. Furthermore, we present a novel bound based on the combination of these two approaches, which is always at least as good as, and in some cases strictly greater than, the maximum of the two bounds. Finally, we present some numerical results to compare the bounds on various graphs.
The rowhammer bug belongs to software-induced hardware faults, and has been exploited to form a wide range of powerful rowhammer attacks. Yet, how to effectively detect such attacks remains a challenging problem. In this paper, we propose a novel approach named RADAR (Rowhammer Attack Detection via A Radio) that leverages certain electromagnetic (EM) signals to detect rowhammer attacks. In particular, we have found that there are recognizable hammering-correlated sideband patterns in the spectrum of the DRAM clock signal. As such patterns are inevitable physical side effects of hammering the DRAM, they can "expose" any potential rowhammer attacks including the extremely elusive ones hidden inside encrypted and isolated environments like Intel SGX enclaves. However, the patterns of interest may become unapparent due to the common use of spread-spectrum clocking (SSC) in computer systems. We propose a de-spreading method that can reassemble the hammering-correlated sideband patterns scattered by SSC. Using a common classification technique, we can achieve both effective and robust detection-based defense against rowhammer attacks, as evaluated on a RADAR prototype under various scenarios. In addition, our RADAR does not impose any performance overhead on the protected system. There has been little prior work that uses physical side-channel information to perform rowhammer defenses, and to the best of our knowledge, this is the first investigation on leveraging EM side-channel information for this purpose.
<p><span>An air-gapped computer is physically isolated from unsecured networks to guarantee effective protection against data exfiltration. Due to air gaps, unauthorized data transfer seems impossible over legitimate communication channels, but in reality many so-called physical covert channels can be constructed to allow data exfiltration across the air gaps. Most of such covert channels are very slow and often require certain strict conditions to work (e.g., no physical obstacles between the sender and the receiver). In this paper, we introduce a new physical covert channel named BitJabber that is extremely fast and strong enough to even penetrate concrete walls. We show that this covert channel can be easily created by an unprivileged sender running on a victim’s computer. Specifically, the sender constructs the channel by using only memory accesses to modulate the electromagnetic (EM) signals generated by the DRAM clock. While possessing a very high bandwidth (up to 300,000 bps), this new covert channel is also very reliable (less than 1% error rate). More importantly, this covert channel can enable data exfiltration from an air-gapped computer enclosed in a room with thick concrete walls up to 15 cm.</span></p>
Moving-target defenses (MTDs) have been widely studied for common general-purpose and enterprise-computing applications. Indeed, such work has produced highly effective, low-overhead defenses that are now commonly deployed in many systems today. One application space that has seen comparatively little focus is that of safety- and mission-critical systems, which are often real-time systems (RTS) with temporal requirements. Furthermore, such systems are increasingly being targeted by attackers, such as in industrial control systems (ICS), including power grids. The strict timing requirements of these systems presents a different design objective than is common in general-purpose applications — systems should be designed around the worst-case performance, rather than the average case. Perhaps in part due to these alternative design considerations, many real-time systems have not benefited from much of the work on software security that common general-purpose and enterprise applications have, despite the ubiquity of real-time systems that actively control so many applications we as a society have come to rely on, from power generation and distribution, to automotive and avionic applications, and many others.This paper explores the application of moving-target defenses in the context of real-time systems. In particular, the worst-case performance of several address-space randomization defenses are evaluated to study the implications of such designs in real-time applications. These results suggest that current moving-target defenses, while performant in the average case, can exhibit significant tail latencies, which can be problematic in real-time applications, especially if such overheads are not considered in the design and analysis of the system. These results inform future research directions for moving-target defenses in real-time applications.
Power grids are undergoing major changes due to the rapid adoption of intermittent renewable energy resources and the increased availability of energy storage devices. These trends drive smart-grid operators to envision a future where peer-to-peer energy trading occurs within microgrids, leading to the development of Transactive Energy Systems. Blockchains have garnered significant interest from both academia and industry for their potential application in decentralized TES, in large part due to their high level of resilience. In this paper, we introduce a novel class of attacks against blockchain based TES, which target the gateways that connect market participants to the system. We introduce a general model of blockchain based TES and study multiple threat models and attack strategies. We also demonstrate the impact of these attacks using a testbed based on GridLAB-D and a private Ethereum network. Finally, we study how to mitigate these attack.
<p><span>Using the Smart Home as a use case, we examine the vulnerabilities in the system across the technologies used in its implementation. A typical smart home will contain a variety of sensors, actuators (e.g. for opening doors), communication links, storage devices, video cameras, network interfaces, and control units. Each of these physical components and subsystems must be secure in order for the overall system to be secure. Typical security analysis focuses on the defined interfaces of the system: network security via firewalls, communications encryption, and authentication at terminals. Unfortunately, many of these devices in the Internet of Things (IoT) space are susceptible to physical attacks via electromagnetic energy, or other sound/heat energy. Properly designed electromagnetic (EM) waveforms can access a range of vulnerabilities, providing unanticipated entry points into the system. In this chapter, we discuss a multi‐modeling methodology for analyzing cyber‐physical vulnerabilities, assessing the system across geometry, electronic, and behavioral domains. A home automation system is used as an example, showing a methodology for assessing vulnerabilities in hardware. The example exploits the use of EM energy injection. A multi‐modeling of the system captures the geometric structure of the hardware with links to behavioral models. Low‐energy EM pathways are discovered that may impact system behavior. Computation is minimized by applying analysis of EM effects only at behavior‐critical inputs and outputs. The chapter also discusses a methodology for system‐level impact analysis. The final conclusion is that susceptibility to physical layer presents many attack surfaces, due to a large number of heterogeneous IoT devices, mandating consideration of the physical dimensions to vulnerability analysis and risk mitigation.</span></p>
2019
The problem of dispatching emergency responders to service traffic accidents, fire, distress calls and crimes plagues urban areas across the globe. While such problems have been extensively looked at, most approaches are offline. Such methodologies fail to capture the dynamically changing environments under which critical emergency response occurs, and therefore, fail to be implemented in practice. Any holistic approach towards creating a pipeline for effective emergency response must also look at other challenges that it subsumes - predicting when and where incidents happen and understanding the changing environmental dynamics. We describe a system that collectively deals with all these problems in an online manner, meaning that the models get updated with streaming data sources. We highlight why such an approach is crucial to the effectiveness of emergency response, and present an algorithmic framework that can compute promising actions for a given decision-theoretic model for responder dispatch. We argue that carefully crafted heuristic measures can balance the trade-off between computational time and the quality of solutions achieved and highlight why such an approach is more scalable and tractable than traditional approaches. We also present an online mechanism for incident prediction, as well as an approach based on recurrent neural networks for learning and predicting environmental features that affect responder dispatch. We compare our methodology with prior state-of-the-art and existing dispatch strategies in the field, which show that our approach results in a reduction in response time with a drastic reduction in computational time.
The adoption of blockchain based distributed ledgers is growing
fast due to their ability to provide reliability, integrity, and auditability
without trusted entities. One of the key capabilities of these emerging
platforms is the ability to create self-enforcing smart contracts. However,
the development of smart contracts has proven to be error-prone in practice,
and as a result, contracts deployed on public platforms are often
riddled with security vulnerabilities. This issue is exacerbated by the design
of these platforms, which forbids updating contract code and rolling
back malicious transactions. In light of this, it is crucial to ensure that a
smart contract is secure before deploying it and trusting it with significant
amounts of cryptocurrency. To this end, we introduce the VeriSolid
framework for the formal verification of contracts that are specified using
a transition-system based model with rigorous operational semantics.
Our model-based approach allows developers to reason about and verify
contract behavior at a high level of abstraction. VeriSolid allows the
generation of Solidity code from the verified models, which enables the
correct-by-design development of smart contracts
publication
Enabling Strong Isolation for Distributed Real-time Applications in Edge Computing Scenarios
Distributed, co-existing applications found in the military and space domains, which operate over managed but shared computing resources at the edge require strong isolation from each other. The state of the art for computation sharing at the edge is traditionally based on Docker and similar pseudo-virtualization features. Our team has been working on an end-to-end architecture that provides strong spatial and temporal isolation similar to what has become standard in avionics communities. In this paper we describe an open-source extension to Linux that we have designed and implemented for our distributed real-time embedded managed systems (DREMS) architecture. The key concepts are the partitioning scheduler, strong security design and a health management interface
Traffic networks are one of the most critical infrastructures for any community. The increasing integration of smart and connected sensors in traffic networks provides researchers with unique opportunities to study the dynamics of this critical community infrastructure. Our focus in this paper is on the failure dynamics of traffic networks. By failure, we mean in this domain the hindrance of the normal operation of a traffic network due to cyber anomalies or physical incidents that cause cascaded congestion throughout the network. We are specifically interested in analyzing the cascade effects of traffic congestion caused by physical incidents, focusing on developing mechanisms to isolate and identify the source of a congestion. To analyze failure propagation, it is crucial to develop (a) monitors that can identify an anomaly and (b) a model to capture the dynamics of anomaly propagation. In this paper, we use real traffic data from Nashville, TN to demonstrate a novel anomaly detector and a Timed Failure Propagation Graph based diagnostics mechanism. Our novelty lies in the ability to capture the the spatial information and the interconnections of the traffic network as well as the use of recurrent neural network architectures to learn and predict the operation of a graph edge as a function of its immediate peers, including both incoming and outgoing branches.
Our results show that our LSTM-based traffic-speed predictors attain an average mean squared error of $6.55\times10^{-4}$ on predicting normalized traffic speed, while Gaussian Process Regression based predictors attain a much higher average mean squared error of $1.78\times10^{-2}$. We are also able to detect anomalies with high precision and recall, resulting in an AUC (Area Under Curve) of 0.8507 for the precision-recall curve. To study physical traffic incidents, we augment the real data with simulated data generated using SUMO, a traffic simulator. Finally, we analyzed the cascading effect of the congestion propagation by formulating the problem as a Timed Failure Propagation Graph, which led us in identifying the source of a failure/congestion accurately.
Bus transit systems are the backbone of public transportation in the United States. An important indicator of the quality of service in such infrastructures is on-time performance at stops, with published transit schedules playing an integral role governing the level of success of the service. However there are relatively few optimization architectures leveraging stochastic search that focus on optimizing bus timetables with the objective of maximizing probability of bus arrivals at timepoints with delays within desired on-time ranges. In addition to this, there is a lack of substantial research considering monthly and seasonal variations of delay patterns integrated with such optimization strategies. To address these, this paper makes the following contributions to the corpus of studies on transit on-time performance optimization: (a) an unsupervised clustering mechanism is presented which groups months with similar seasonal delay patterns, (b) the problem is formulated as a single-objective optimization task and a greedy algorithm, a genetic algorithm (GA) as well as a particle swarm optimization (PSO) algorithm are employed to solve it, (c) a detailed discussion on empirical results comparing the algorithms are provided and sensitivity analysis on hyper-parameters of the heuristics are presented along with execution times, which will help practitioners looking at similar problems. The analyses conducted are insightful in the local context of improving public transit scheduling in the Nashville metro region as well as informative from a global perspective as an elaborate case study which builds upon the growing corpus of empirical studies using nature-inspired approaches to transit schedule optimization.
Services hosted in multi-tenant cloud platforms often encounter performance interference due to contention for non-partitionable resources, which in turn causes unpredictable behavior and degradation in application performance. To grapple with these problems and to define effective resource management solutions for their services, providers often must expend significant efforts and incur prohibitive costs in developing performance models of their services under a variety of interference scenarios on different hardware. This is a hard problem due to the wide range of the possible co-located services and their workloads, and the growing heterogeneity in the runtime platforms including the use of fog and edge-based resources, not to mention the accidental complexities in conducting such application profiling under a variety of scenarios. To address these challenges, we present FECBench (Fog/Edge/Cloud Benchmarking), which is an open source framework comprising a set of 106 applications covering a wide range of application classes that guides providers in building performance interference prediction models for their services without incurring undue costs and efforts via the following contributions. First, we define a technique to build resource stressors that can stress multiple system resources all at once in a controlled manner, which help to gain insights into the impact of interference on the application’s performance. Second, to overcome the need for exhaustive application profiling, FECBench intelligently uses the design of experiments (DoE) approach to enable users to build surrogate performance models of their services. Third, FECBench maintains an extensible knowledge base of application combinations that create resource stress across the multi-dimensional resources design space. Empirical results using real-world scenarios to validate the efficacy of FECBench shows that the predicted application performance using the surrogate models incurs a median error of only 7.6 percent across all tests, with 5.4 percent in the best case and 13.5 percent in the worst case.