The 5th AI City Challenge

The AI City Challenge was created with two goals in mind: (1) pushing the boundaries of research and development in intelligent video analysis for smarter cities use cases, and (2) assessing tasks where the level of performance is enough to cause real-world adoption. Transportation is a segment ripe for such adoption. The fifth AI City Challenge attracted 305 participating teams across 38 countries, who leveraged city-scale real traffic data and high-quality synthetic data to compete in five challenge tracks. Track 1 addressed video-based automatic vehicle counting, where the evaluation being conducted on both algorithmic effectiveness and computational efficiency. Track 2 addressed city-scale vehicle re-identification with augmented synthetic data to substantially increase the training set for the task. Track 3 addressed city-scale multi-target multi-camera vehicle tracking. Track 4 addressed traffic anomaly detection. Track 5 was a new track addressing vehicle retrieval using natural language descriptions. The evaluation system shows a general leader board of all submitted results, and a public leader board of results limited to the contest participation rules, where teams are not allowed to use external data in their work. The public leader board shows results more close to real-world situations where annotated data is limited. Results show the promise of AI in Smarter Transportation. State-of-the-art performance for some tasks shows that these technologies are ready for adoption in real-world systems.

Introduction
The proliferation of sensors has led to the production of fast and voluminous data, along with the emergence and increasing adoption of 5G technologies. The ability to process such voluminous data at the edge has created unique opportunities for extracting insights using the Internet of Things (IoT) for increased operational efficiencies and improved overall outcomes. Intelligent Transportation Systems (ITS) seem ripe to benefit from the adoption of artificial intelligence (AI) applied at the edge. The AI City Challenge was intended to bridge the gap between realworld city-scale problems in ITS and the cutting edge research and development in intelligent video analytics. The challenge is based on data that reflect common scenarios in city-scale traffic management. It also provides an evaluation platform for algorithms to be compared using common metrics. Throughout the past four years of this challenge, we have developed progressively more complex and relevant tasks [29,30,31,32].
The fifth edition of this annual challenge, in conjunction with CVPR 2021, continues to push the envelope of research and development in the context of real-world application in several new ways. First, the challenge has introduced a new track for multi-camera retrieval of vehicle trajectories based on natural language descriptions of the vehicles of interest. To our knowledge, this is the first such challenge that combines computer vision and natural language processing (NLP) for city-scale retrieval implementations needed by the Departments of Transportation (DOTs) for operational deployments. The second change in this edition is the expansion of training and testing sets in several challenge tracks. Finally, the vehicle counting track now requires an online, rather than batch algorithm approach to qualify for winning the challenge. Deployment on an edge IoT device helps bring the advances in this field closer to real-world deployment.
The five tracks of the AI City Challenge 2021 are summarized as follows: • Multi-class multi-movement vehicle counting using IoT devices: Vehicle counting is an essential and pivotal task in various traffic analysis activities. The capability to count vehicles under specific movement patterns or categories from a vision-based system is useful yet challenging. This task counts four-wheel vehicles and freight trucks that follow pre-defined movements from multiple camera scenes with online algorithms which should run efficiently on edge devices. The dataset contains 31 video clips of about 9 hours in total that are captured from 20 unique traffic camera views.
• Vehicle re-identification with real and synthetic training data: Re-identification (ReID) [58,60] aims to establish identity correspondences across different cameras. Our ReID task is evaluated on an expanded version of the previous dataset, referred to as CityFlowV2-ReID, which contains over 85,000 vehicle crops captured by 46 cameras placed in multiple traffic intersections. Some of the images are as small as 1,000 pixels. A synthetic dataset [53,46] along with a simulation engine is provided for teams to form augmented training sets.
• City-scale multi-target multi-camera vehicle tracking: Teams are asked to perform multi-target multicamera (MTMC) vehicle tracking, whose evaluation is conducted on an updated version of our dataset, referred to as CityFlowV2. The annotations on the training set have been refined to include ∼60% more bounding boxes to align with the labeling standard of the test set. There are in total 313, 931 bounding boxes for 880 distinct annotated vehicle identities.
• Traffic anomaly detection: In this track, teams are required to detect anomalies in videos such as crashes, stalled vehicles, etc. The dataset used in this track is obtained from video feeds captured at multiple intersections and highways in Iowa, USA. The training set consists of 100 videos, including 18 anomalies, while the test set consists of 150 videos. Each video is in 800×410 resolution and around 15 minutes long.
• Natural language-based vehicle retrieval: This newly added task offers natural language (NL) descriptions for teams to specify corresponding vehicle track queries. Participant teams need to perform vehicle retrieval given single-camera tracks and the NL labels. The performance is evaluated using standard retrieval metrics.
Continuing the trend of previous editions, this year's AI City Challenge has attracted strong participation, especially with regards to the number of submissions to the evaluation server. We had a total of 305 participating teams that included more than 700 individual researchers from 234 recognized institutions in 38 countries. There were 194, 235, 232, 201, and 155 participation requests received for the 5 challenge tracks, respectively. Of all requesting teams, 137 registered for an account on the evaluation system, and 21,51,35,15, and 20 teams submitted results to the leader boards of the 5 tracks, respectively. Overall, the teams completed 1,685 successful submissions to the evaluation system across all tracks.
This paper presents a detailed summary of the preparation and results of the fifth AI City Challenge. In the following sections, we describe the challenge setup ( § 2), challenge data preparation ( § 3), evaluation methodology ( § 4), analysis of submitted results ( § 5), and a brief discussion of insights and future trends ( § 6).

Challenge Setup
The fifth AI City Challenge was set up following a similar format as in previous years. The training and test sets were made available to the participants on January 22, 2021. All challenge track submissions were due on April 9, 2021. Similar to the earlier editions, all candidate teams for awards were requested to submit their code for validation. The performance on the leader boards has to be reproducible without the use of external data.
In the released datasets, private information such as vehicle license plates and human faces have been redacted manually. Detailed descriptions of the challenge tasks are as follows.
Track 1: Multi-class multi-movement vehicle counting. Teams were asked to count four-wheel vehicles and freight trucks that followed pre-defined movements from multiple camera scenes. For example, teams performed vehicle counting separately for left-turning, right-turning, and through traffic near a given intersection. This helps traffic engineers understand the traffic demand and freight ratio on individual corridors. Such knowledge can be used to design better intersection signal timing plans and the consideration of traffic congestion mitigation strategies when necessary. To maximize the practical value of the challenge outcome, both vehicle counting effectiveness and the program execution efficiency contributed to the final score evaluation. Additionally, to mimic the performance of in-road hardware sensor-based counting systems, methods were required to run online in real-time. While any system could be used to generate solutions to the problem for general submissions, the final evaluation of the top methods will be executed on an IoT device. The team with the highest combined efficiency and effectiveness score will win this track.
Track 2: Vehicle ReID with real and synthetic training data. Teams were requested to perform vehicle ReID based on vehicle crops from multiple cameras placed at several road intersections. This helps traffic engineers understand journey times along entire corridors. Similar to the previous edition of the challenge, the training set was composed of both real and synthetic data. The usage of synthetic data was encouraged as the simulation engine was provided to create large-scale training sets. The team with the highest accuracy in identifying vehicles that appeared in different cameras will be declared the winner of this track.
Track 3: City-scale MTMC vehicle tracking. Teams were asked to track vehicles across multiple cameras at a single intersection and across multiple intersections spreading out in a mid-size city. Results can be used by traffic engineers to understand traffic conditions at a city-wide scale. The team with the highest accuracy in tracking vehicles that appear in multiple cameras will be declared as the winner. In the event that multiple teams perform equally well in this track, the algorithm needing the least amount of manual supervision will be chosen as the winner.
Track 4: Traffic anomaly detection. Based on more than 62 hours of videos collected from different camera views at multiple freeways by the DOT of Iowa, each team was asked to submit a list of at most 100 detected anomalies. The anomalies included single and multiple vehicle crashes and stalled vehicles. Regular congestion was not considered as an anomaly. The team with the highest average precision and the most accurate anomaly starting time prediction in the submitted events will become the winner of this track.
Track 5: NL based vehicle retrieval. In this new challenge track, teams were asked to perform vehicle retrieval given single-view tracks and corresponding NL descriptions of the targets. The performance of the retrieval task was evaluated using the standard metrics of retrieval tasks (e.g., Mean Reciprocal Rank (MRR), Recall@N, etc.), while ambiguities caused by similar vehicle types, colors, and motion types were considered as well. The NL based vehicle retrieval task offered unique challenges versus action recognition tasks and content-based image retrieval tasks. In particular, different from prior content-based image retrieval systems [11,14,28], retrieval models for this task needed to consider both the relation contexts between vehicle tracks and the motion within each track. While traditional action recognition by NL description [2] localizes a moment within a video, the NL based vehicle retrieval task requires both temporal and spatial localization within a video.

Datasets
The data used in this challenge were collected from traffic cameras placed in multiple intersections of a mid-size city in USA and the state highways in Iowa. Video feeds have been synchronized manually and the GPS information for some cameras were made available for researchers to leverage the spatio-temporal information. The majority of these video clips are of high resolution (1080p) at 10 frames per second. We have addressed the privacy issues by carefully redacting all vehicle license plates and human faces. In addition to the datasets used in the previous editions of the challenge, a new NL based vehicle retrieval dataset was added for a separate challenge track this year.

The CityFlowV2 dataset
The CityFlow benchmark [47,31] was first introduced in the third AI City Challenge in 2019. To the best of our knowledge, it was the first benchmark to address MTMC vehicle tracking in a city scale. A subset of image crops was also created for the task of vehicle ReID. However, there were several issues with this initial release. (1) Many annotations were labeled not properly or missing especially for small-sized objects. (2) The training set was too small compared with the test set, and a validation set was needed.
(3) The leading teams in previous years have saturated the performance on the ReID test set.
To continue to challenge the participants, we have upgraded the benchmark in multiple ways this year, and the new version is referred to as CityFlowV2. First, we manually refined the annotations of the dataset, especially for the training set, to correct mislabeled objects and include bounding boxes that are as small as 1, 000 pixels. Besides, a new test set containing 6 cameras at multiple intersections on a city highway was introduced in the fourth AI City Challenge. The distance between the two furthest cameras was 4 km. Moreover, the original test set was adapted to be the validation set for teams to better analyze and improve their models. The number of total bounding boxes has thus grown from 229, 680 to 313, 931, whereas the distinct vehicle identities also increased from 666 to 880. Finally, we re-sampled the ReID set for Track 2 with small-sized bounding boxes included, and now there are 85, 058 images versus 56, 277 in the earlier version.
In summary, CityFlowV2 consisted of 3.58 hours (215.03 minutes) of video captured by 46 cameras spanning 16 intersections. The dataset was divided into 6 simultaneous scenarios, where 3 were used for training, 2 for validation, and the other one for testing. Only vehicles that passed through more than one camera were labeled. In each scenario, the time offset and geographic location of each video were provided so that spatio-temporal knowledge can be utilized. The subset for vehicle ReID, namely CityFlowV2-ReID, was split into a training set with 52, 717 images from 440 identities, and a test set including 31, 238 images from another 440 identities. An additional 1, 103 images were sampled as queries. We also provided in the package evaluation and visualization tools to facilitate the quantitative and qualitative analysis of the results.

The VehicleX dataset
The VehicleX dataset [53,46] was first introduced in the fourth AI City Challenge in 2020. It has a large number of different types of backbone models and textures that were hand-crafted by professional 3D modelers. To the best of our knowledge, it is currently the largest publicly available 3D vehicle dataset with 11 vehicle types and 272 backbones. Rendered by Unity [17], a team can potentially generate an unlimited number of identities and images by editing various attributes. In this year's AI City Challenge, 1,362 identities and more than 190,000 images were generated for joint training with the real-world datasets (i.e., CityFlowV2-ReID) to improve the ReID accuracy. We also provided the Unity-Python interface for participant teams, so they could create more synthetic data if needed. They were enabled to generate new identities using a different color on backbones or generate more images with various orientations, camera parameters, and lighting settings. With these attributes, participants can perform multi-task learning, which would improve the ReID accuracy [46,23].
In order to minimize the domain gap between the synthetic data and real-world data, a two-level domain adaptation method was performed as shown in Fig. 1. First, on the content level via the Unity-Python interface, an attribute descent [53] approach was incorporated to guide the VehicleX data in approximating key attributes in real-world datasets. For example, attributes including vehicle orientation, lighting settings, camera configurations, etc. in the VehicleX en-gine were successively adjusted according to the Fréchet Inception Distance (FID) between synthetic data and real data. Secondly, on the appearance (style) level, SPGAN [6] was used to further adapt the style of the synthetic images to better match that of real-world data. The above two-level adaptation method significantly reduced the domain discrepancy between simulated and real data, thereby making VehicleX images visually plausible and similar to the real-world ones.

Vehicle counting dataset
This year, we adopted the same vehicle counting dataset that was introduced in the fourth AI City Challenge [32]. The vehicle counting data set contains 31 video clips (about 9 hours in total) captured from 20 unique camera views. Some cameras provide multiple video clips to cover different lighting and weather conditions. Videos are 960p or better, and most have been captured at 10 frames per second. The ground truth counts for all videos were manually created and cross-validated by multiple annotators.

Iowa DOT anomaly dataset
This year, we are using an extended anomaly dataset compared to the one used in the fourth AI City Challenge [32]. The Iowa DOT anomaly dataset consists of 100 video clips in the training set and 150 videos in the test set, compared to the 100 videos each in the training and test sets used in 2020. Video clips were recorded at 30 frames per second at a resolution of 800 × 410. Each video clip is approximately 15 minutes in duration and may include a single or multiple anomalies. If a second anomaly is reported while the first anomaly is still in progress, it is counted as a single anomaly. The traffic anomalies consist of single or multiple vehicle crashes and stalled vehicles. A total of 18 such anomalies present in the training set across 100 clips.

The CityFlow-NL Dataset
The CityFlow-NL benchmark [8] consists of 666 target vehicles in 3, 028 single-view tracks from 40 calibrated cameras and 5, 289 unique NL descriptions. For each target, NL descriptions were provided by at least three crowdsourcing workers, to better capture realistic variations and ambiguities that are expected in the real-world application domains. The NL descriptions describe the vehicle color, vehicle maneuver, traffic scene and relations with other vehicles. Example NL descriptions and targets are shown in Fig. 2.
For the NL-based retrieval task, we utilize the CityFlow-NL benchmark in a single-view setup, although the CityFlow-NL can be potentially used for retrieval tasks with multi-view tracks. For each single-view vehicle track, we bundled it with a query consisting of three different NL descriptions for training. During testing, the goal is to retrieve and rank vehicle tracks based on the given NL queries.

Evaluation Methodology
Similar to previous AI City Challenges [30,31,32], teams could submit multiple runs (20 for Tracks 2, 3 and 5, and 10 for Tracks 1 and 4) for each track to an online evaluation system that automatically measured the effectiveness of results upon submission. Submissions were limited to five per day, and any submissions that lead to a format or evaluation error did not count against a team's daily or maximum submission totals. During the competition, the evaluation system showed the team's own performance, along with the top-3 best scores on the leader boards (without revealing identifying information of those teams). To discourage excessive fine-tuning to improve performance, the results shown to the teams prior to the end of the challenge were computed on a 50% subset of the test set for each track. After the challenge submission deadline, the evaluation system revealed the full leader boards with scores computed on the entire test set for each track.
Teams competing for the challenge prizes were not allowed to use external data or manual labeling to fine-tune the performance of their model, and those results were published on the Public leader board. Teams using additional external data or manual labeling were allowed to submit to a separate General leader board.

Track 1 evaluation
For the first time this year, the multi-class multimovement vehicle counting task required the creation of online algorithms that could generate results in real time. The Track 1 evaluation score (S1) was computed in the same way as in the fourth edition [32], however ignoring results that would have been produced more than 15 seconds behind real-time playback of the input video. The filtering was done based on self-reported output timestamps which were added to the submission format for the Track 1 challenge. Since efficiency scores reported by teams are not easily normalized, competition prizes will only be awarded based on the scoring obtained when executing the submitted codes from participant teams on the held-out Track 1 Dataset B. To ensure comparison fairness, Dataset B experiments will be executed on the same device. Also new this year, the target device is an IoT device that could easily be deployed in the field, close-by to the traffic cameras, thereby reducing the need for expensive data transfers to centralized data centers. The target device this year is an NVIDIA Jetson NX development kit.

Track 2 evaluation
The Track 2 accuracy evaluation metric was the mean Average Precision (mAP) [57] of the top-K matches, which measured the mean of average precision, i.e., the area under the Precision-Recall curve (AUC) over all the queries. In this track, K = 100. Our evaluation server also provided other measures, such as the rank-1, rank-5 and rank-10 hit rates, which measured the percentage of the queries that had at least one true positive result ranked within the top 1, 5 or 10 positions, respectively. While these scores were shared with the teams for their own submissions, they were not used in the overall team ranking and were not displayed in the leader boards.

Track 3 evaluation
The task of Track 3 was detecting and tracking targets across multiple cameras. Baseline detection and singlecamera tracking results were provided, and teams were also ComeniusU [19] 0.8449 allowed to use their own methods. Similar to previous years, the IDF1 score [38] was used to rank the performance of each team, which measured the ratio of correctly identified detections over the average number of ground-truth and computed detections. The evaluation tool provided with our dataset also computed other evaluation measures adopted by the MOTChallenge [4,21], such as multiple object tracking accuracy (MOTA), multiple object tracking precision (MOTP), mostly tracked targets (MT) and false alarm rate (FAR). However, they were not used for ranking purposes.
The measures that were displayed in the evaluation system were IDF1, IDP, IDR, Precision (detection), and Recall (detection).

Track 4 evaluation
Track 4 performance was measured in the same way as in earlier editions, by combining the detection performance, measured by the F 1 score, and detection time error, measured via the normalized root mean square error of the predicted accident times. For full details on the evaluation metric, please see [32].

Track 5 evaluation
The NL based vehicle retrieval task was evaluated using standard metrics for retrieval tasks [27]. We used the Mean Reciprocal Rank (MRR) as the main evaluation metric. Re-call@5, Recall@10 and Recall@25 were also evaluated for all models but were not used in the ranking. For a given set Q of queries, the MRR score is computed as where rank i refers to the rank position of the first relevant document for the i-th query; |Q| is the set size.

Summary for the Track 1 challenge
Considering the new on-line performance requirement added this year, teams have put in efforts to balance out effectiveness versus efficiency by designing more computationally efficient algorithms. Similar to last year, a stepby-step detection-tracking-counting (DTC) framework remained the most popular approach among top-performing teams. There were also new designs not following the DTC framework, which emphasized more on improving execution efficiency.
The top 4 teams [25,12,48,49] on the public leader board all followed the DTC framework. All four teams employed YOLO-family models (where [25] chose PP-YOLO, [12] chose YOLOv4-tiny, [48] chose YOLOv5, and [49] chose scaled YOLOv4) for vehicle detection. This indicates the popularity of the YOLO models in offering good accuracy as well as computational efficiency. In the tracking step, all four teams adopted the popular SORT tracking strategy with key steps including linear motion prediction, feature extraction, data association, and Kalman filter updates. To accommodate on-line execution requirements, teams either directly used bounding box IOU for data association [48] or a combination of simpler features including color histogram, motion and shape features, instead of using deep CNN appearance features [25,12,49].
The Baidu-SYSU team [25] adopted hand-engineered spacial filters to remove all bounding boxes outside the ROIs before the tracking step, which was simple and effective in suppressing noise. The HCMIU team [12] designed a three-fold data association scheme with multiple criteria checkers in a conditional cascade fashion to minimize the computational cost. In the counting step, teams manually drew movement represented tracks and used handengineered ROI filters and customized similarity metric to assist vehicle movement assignment. The similarity metric in [25] combined Hausdorff distance and the angle between directions. Some teams [48,49] computed Hausdorff distance on each divided sub-segment to count directionality. The HCMIU team [12] first applied customized ROIs as filters to make sure all the rest tracks belong to one of the MOIs and then assigned movements by cosine similarity. Additionally, they also implemented thread-level parallelism to boost both robustness and efficiency of their method.
The non-DTC frameworks in [10,19] also showed competitive results. The CenterTrack object detection and tracking network in [19] generated vehicle bounding boxes as well as location displacement vectors in two consecutive framesin an end-to-end manner (instead of performing detection and tracking in two separated steps). The localization-based tracking (LBT) in [10] only detected vehicles on candidate crops from either designated source regions or predicted locations (of already tracked vehicles). This can effectively avoid repeated object detection on the entire frame. Both source regions and sink regions were manually defined. Their strategy led to reduced compu- tation workloads, as only the vehicles from the source regions were detected and tracked. Vehicle movement was determined based on the combination of the source/sink region of a tracked vehicle. The LBT counting scheme was claimed 52% faster than the regular DTC framework.

Summary for the Track 2 challenge
Most methods took advantage of the provided synthetic data generator to enhance the real training data. Some teams [26,15,52] adopted schemes, e.g., MixStyle [59] and Balanced Cross-Domain Learning, for domain adaptation. For example, the top performing team [26] used unsupervised domain-adaptive (UDA) training to strengthen the robustness. The team from SJTU [51] leveraged synthetic data to learn vehicle attributes that better captured appearance features. The other leading team from Baidu-UTS [16] proposed a novel part-aware structure-based ReID framework to handle appearance change due to pose and illumination variants. Many teams [43,9] also extracted videobased features based on query expansion and temporal pooling that suppressed noise in the individual images. Finally, teams reported that post-processing strategies, including reranking, image-to-track retrieval, and inter-camera fusion, were useful in improving their methods' effectiveness.

Summary for the Track 3 challenge
All participant teams followed the typical processing steps for the MTMC vehicle tracking task, including object detection, multi-target single-camera (MTSC) tracking, appearance feature extraction for ReID, and cross-camera tracklet matching. The two best performing teams from Alibaba-UCAS [24] and Baidu [54] utilized state-of-theart MTSC tracking schemes, e.g., JDETracker [55] and TPM [36], instead of the provided baseline [45,13] to generate more reliable tracklets. Likewise, the SJTU team [51]  employed a tracker update strategy to improve the traditional Kalman-filter-based tracking. These teams also leveraged spatial-temporal knowledge and traffic rules to create crossroad zones or entry/exit ports to construct a better distance matrix for tracklet clustering. The Fraunhofer team [42] proposed an occlusion-aware approach that discarded obstacle-occluded bounding boxes and overlapping tracks for more precise matching. Other teams [52,41,22] also utilized a similar pipeline to extract local trajectories and perform matching using ReID features.

Summary for the Track 4 challenge
The methodologies of the top performing teams in Track 4 of the challenge were based on the basic idea of preprocessing, which involved background modelling, vehicle detection, road mask construction to remove stationary parked vehicles, and abnormal vehicle tracking. The dynamic tracking module of the winning team, Baidu-SIAT [56], utilized spatio-temporal status and motion patterns to determine the accurate starting time of the anomalies. Post-processing was performed to further refine the starting time of the traffic anomalies. Their best score was 0.9355, indicating that the problem of traffic anomaly can be solved using current technology. The runner-up, ByteDance [50] made use of box-level tracking of the potential spatio-temporal anomalous tubes. Their method can accurately detect the anomalous time periods using such tubes obtained from background modeling and refinements. Similarly, the third-place team, WHU [5], also leveraged box-level and pixel-level tracking to identify anomalies along with a dual modality bi-directional tracing module, which can further refine the time periods.

Summary for the Track 5 challenge
For the NL-based vehicle retrieval task, most teams [3,44,33,40,18,20,39] chose to obtain sentence embeddings of the queries, while two teams [34,35] used con-ventional NLP techniques to process the NL queries. For the cross-modality learning, some teams [40,3] utilized the ReID models (approaches from the Track 2 challenge). The adoption of vision models pre-trained on visual ReID data showed improvements from their corresponding baselines. Vehicle motion is an essential part of the NL descriptions in CityFlow-NL. Therefore, some teams [3,20,35] developed specific approaches to measure and represent the vehicle motion patterns.
The best performing model [3] considered both local (visual) and global representations of the vehicle trajectories to encode vehicle motion. In addition, NL augmentation via language translation was used to improve the performance of the retrieval. The second best performing model [44] used GloVe and a custom built gated recurrent unit (GRU) to measure the similarity between visual crops and the query. The method in [20] retrieved the target vehicle by performing per-frame segmentation, which can be derived as a visual tracker. However, the performance of this tracker was sub-optimal. [34] used semantic role labeling techniques on the NL descriptions to rank and retrieve the vehicle tracks. [35] not only considered the vehicle motion but also relations w.r.t. other vehicles described in the NL queries. This approach yielded the best performing model not relying on sentence embeddings for similarity measurements.

Conclusion
The fifth edition of the AI City Challenge continues to attract worldwide research community participation in terms of both quantity and quality. A few observations are noted below.
The main thrust of Track 1 this year was the evaluation of counting methods on edge IoT devices. To this end, teams have put significant efforts in optimizing algorithms as well as implementation pipelines for performance improvement. The detection-tracking-counting (DTC) framework remained the most popular scheme among top-performing teams [25,12,48,49]. Within the DTC framework, object tracking was the focus of greater attention. Methods not using deep-appearance-based features proved to be both effective and cost-efficient in the feature extraction and data association. We have also seen innovative designs [10,19] not following the DTC framework and instead emphasizing on execution efficiency and showing competitive results.
In Tracks 2, 3 and 4, we have significantly expanded the datasets, which motivated teams to train more robust models that could be applied to diverse scenarios. In Track 2, we made major improvements to the Unity-Python interface of the synthetic data generator that enabled teams to render vehicle identities of various colors, orientations, camera parameters, light settings, etc. The top-ranked teams on the leader board leveraged UDA schemes to stabilize training across different domains that resulted in their remarkable performance. In Track 3, a new test set has been added since the fourth edition of the Challenge and the labels of bounding boxes have been largely refined to include more small-sized objects. To tackle this challenging problem, teams utilized state-of-the-art tracking methods to create reliable tracklets and introduced cross-camera matching algorithms based on spatio-temporal information as well as traffic rules and topological structures. As for Track 4, the test set has grown by 150% compared to the fourth edition in the last year. We have seen teams adopting different types of approaches to detect anomalies, including tracking-based algorithms, background modeling, motion pattern understanding, etc.
In Track 5, we proposed a novel challenge for NL based vehicle retrieval. Teams were challenged to apply knowledge across computer vision and NLP to the identification of proper vehicle tracks. Various approaches were introduced by teams to create representative motion features and appearance embeddings. Compared to the other challenge tracks, the performance of the leading teams was far from saturation due to multiple factors. It was difficult to relate the semantic labels to vehicle attributes especially for some that exhibited long tails in the distribution. Moreover, the motion patterns of vehicles required to be described using tracking techniques in 3D space and thus were hard to train directly through NL descriptors. Finally, many vehicles shared similar colors and types, which forced the algorithms to distinguish targets through fine-grained details, a well-known issue for deep learning frameworks.
Future work for the AI City Challenge will continue pushing the twin objectives of advancing the state of the art and bridging the real-world utility. To this end, while we will continue to increase the dataset sizes, we hope to find forward-thinking DOTs that will provide a platform to deploy some of the most promising approaches emerging out of the AI City Challenge in their operational environments. This new approach will also likely require developing novel evaluation metrics to compare previous status quo baselines with the state-of-the-art AI-based systems developed in the challenge. We believe such a collaboration would make the challenge a truly unique opportunity for ITS applications in the real world and would be of great benefit to the DOTs.

Acknowledgment
The datasets of the fifth AI City Challenge would not have been possible without significant contributions from the Iowa DOT and an urban traffic agency in the United States. This challenge was also made possible by significant data curation help from the NVIDIA Corporation and academic partners at the Iowa State University, Boston University, Lafayette College, Indian Institute of Technology, Kanpur and Australian National University.


Fault Attacks on CCA-secure Lattice KEMs

NIST’s post-quantum standardization effort very recently entered its final round. This makes studying the implementation-security aspect of the remaining candidates an increasingly important task, as such analyses can aid in the final selection process and enable appropriately secure wider deployment after standardization. However, lattice-based key-encapsulation mechanisms (KEMs), which are prominently represented among the finalists, have thus far received little attention when it comes to fault attacks. Interestingly, many of these KEMs exhibit structural similarities. They can be seen as variants of the encryption scheme of Lyubashevsky, Peikert, and Rosen, and employ the Fujisaki-Okamoto transform (FO) to achieve CCA2 security. The latter involves re-encrypting a decrypted plaintext and testing the ciphertexts for equivalence. This corresponds to the classic countermeasure of computing the inverse operation and hence prevents many fault attacks. In this work, we show that despite this inherent protection, practical fault attacks are still possible. We present an attack that requires a single instruction-skipping fault in the decoding process, which is run as part of the decapsulation. After observing if this fault actually changed the outcome (effective fault) or if the correct result is still returned (ineffective fault), we can set up a linear inequality involving the key coefficients. After gathering enough of these inequalities by faulting many decapsulations, we can solve for the key using a bespoke statistical solving approach. As our attack only requires distinguishing effective from ineffective faults, various detection-based countermeasures, including many forms of double execution, can be bypassed. We apply this attack to Kyber and NewHope, both of which belong to the aforementioned class of schemes. Using fault simulations, we show that, e.g., 6,500 faulty decapsulations are required for full key recovery on Kyber512. To demonstrate practicality, we use clock glitches to attack Kyber running on a Cortex M4. As we argue that other schemes of this class, such as Saber, might also be susceptible, the presented attack clearly shows that one cannot rely on the FO transform’s fault deterrence and that proper countermeasures are still needed.

Introduction
The search for quantum secure replacements of RSA and DLP-based cryptosystems is in full swing. This is demonstrated by NIST's ongoing Post-Quantum Cryptography Standardization process [NIS16], which very recently entered its third and final round. In this selection effort, a large number of submitted proposals base their security arguments on lattice problems. Such lattice-based key-encapsulation mechanisms (KEMs) and digital

Algorithm 2 LPR Encryption
Input: Public key pk = (a, b), n-bit message m Output: Ciphertext (u, v) 1: r, e 1 , e 2 ∈ R q ← χ n 2: u = ar + e 1 3: v = br + e 2 + m · q/2 4: return (u, v) 2 Background In the following, [a, b) represents an open-closed interval, whereas [a, b] includes both boundary values. We denote vectors and polynomials using lower-case characters, like s, individual coefficients of s are written as s [i]. Upper-case symbols like A denote matrices. Multiplication of polynomials a, b in some ring R is denoted as a · b or simply ab. (Coefficient-wise) sampling from a probability distribution is represented with ←, deterministic assignments with =, and equality tests with ==. This corresponds to the C programming language, which is used in all following source code excerpts.

LPR Public-Key Encryption
In 2010, Lyubashevsky, Peikert, and Regev [LPR10] extended Regev's Learning With Errors (LWE) problem [Reg05] to an algebraic variant called Ring-LWE (RLWE). They also defined a public-key encryption scheme, frequently dubbed the LPR scheme, which offers a reduction to RLWE. The LPR cryptosystem uses polynomials in the ring R q = Z q [x]/(x n + 1), with a prime q and n a power of two. The parameters q and n are typically chosen such that polynomial multiplication can be performed in O(n log n) using the Number Theoretic Transform (NTT). LPR requires sampling from a (narrow) error distribution χ. Early proposals, such as the original LPR scheme, used a discrete Gaussian distribution for χ. However, Gaussian samplers are hard to implement securely. For this reason, many newer proposals, including Kyber and NewHope, use a centered binomial distribution over the range [−η, η] for some small integer η.
The encryption scheme is comprised of three procedures. Algorithm 1 (Key Generation) generates a public/secret key pair. The coefficients of the secret key s and the noise polynomial e are drawn from χ, the coefficients of a are sampled from U q , i.e., from the uniform distribution over Z q . The public key b is computed as b = as + e. While only s is stored as part of the secret key, we note that e must also be considered a secret, as knowing its value would allow trivial recovery of s. Encryption is shown in Algorithm 2. In its first step, three polynomials r, e 1 , e 2 are sampled from the error distribution. Then, the two ciphertext components u, v are computed. For computing the second component v, the n-bit message m needs to be mapped to a polynomial in R q . The simplest way of doing that is by multiplying each bit of m with q/2 . Finally, Algorithm 3 specifies the decryption step. Its correctness can be verified by back-substitution: As seen above, computing m = v − us yields a noisy version of the plaintext. We call the added terms, i.e., er + e 2 − e 1 s, the encryption noise d. As all terms involved in this encryption noise are sampled from the narrow error distribution χ, the original message bits can still be recovered. This can be seen in Figure 1, which shows an exemplary probability distribution for the coefficients of the noisy plaintext in two different ranges. The probability distribution of a 0 bit is shown with a solid line; the dashed line shows the distribution for a 1 bit. We use this mapping throughout the rest of this paper.
A dedicated decoding routine Decode is needed to recover the original message m from m . We defer the description of efficient constant-time decoder implementations to later sections.

Fujisaki-Okamoto Transform
The LPR public-key encryption scheme only offers security against chosen-plaintext attacks (CPA). Thus, LPR key pairs must be ephemeral, as the plain scheme can be trivially broken in the chosen-ciphertext setting (CCA) if keys are reused (see, e.g., [Flu16]). For this reason, many LPR-based schemes make use of the Fujisaki-Okamoto (FO) transform [FO99] or one of its more recent versions [TU16,HHK17]. This transform allows constructing a CCA-secure key-exchange mechanism (KEM) using a CPA-secure public-key encryption scheme.
The employed FO variants are, at least from a high-level perspective, very similar. To illustrate the basic principles of the transform, we now give more details on the FO variant used by NewHope [PAA + 19]. NewHope refers to its key-encapsulation transformation as QFO ⊥ m . It embeds a public-key encryption scheme PKE featuring key generation, encryption, and decryption. Crucially, the randomness required for encryption is made explicit via a seed parameter coin. Furthermore, let F and G be two hash functions. Figure 2 shows the full QFO ⊥ m process. In Encaps, a randomly chosen message µ is encrypted using a seed derived via G. The shared secret ss is computed by hashing Keygen() Encaps(pk) Decaps((c, d), (sk, pk, s)) (pk, sk) = PKE.KeyGen() s ← {0, . . . , 255} lens sk = (sk, pk, s) return (pk, sk) the PKE-ciphertext c together with the confirmation value d. Decapsulation recovers the message µ and then re-encrypts it using the recovered seed coin. Only if both the PKE-ciphertexts as well as the confirmation values d match, the correct shared secret is returned. Upon failure, a pseudorandom shared secret is computed.
While the intended purpose of the FO is to establish CCA security, it also averts many fault attacks by design. For instance, when targeting PKE.Decrypt in Decaps, i.e., the only part involving the private key sk, all faults leading to a corrupted µ are detected, as re-encryption will lead to a different c . This rules out differential fault attacks exploiting resulting differences in µ .

Kyber
Kyber [ABD + 19] is one of four finalists in the KEM category of the NIST PQC standardization process. It is an example of a scheme combining an LPR-like public-key encryption scheme with the FO to construct a CCA-secure KEM. The Kyber second-round specification includes three parameter sets (Kyber512, Kyber768, and Kyber1024), which are listed in Table 2 of Appendix A. Structure and differences. Unlike LPR, Kyber bases its security on the Learning with Errors problem in module lattices (Module-LWE). This means that, e.g., a is not a polynomial, but instead a quadratic matrix of polynomials A ∈ R k×k q , where k is the module rank. Other elements, such as the secret key s, the error e, as well as r and e 1 , are now (column) vectors containing polynomials, i.e., R k q . Kyber uses the same base ring R q for all its parameter sets, only the module rank k varies. All parameters are chosen such that polynomial multiplication can be efficiently implemented using a slightly modified NTT.
Another difference to plain LPR is the use of (lossy) ciphertext compression. In compression, a value x is divided by q/2 d , with d being the compression parameter, and then rounded to the nearest integer. Decompression reverses this process, but can of course only recover an approximation to x. In simplified terms, only the d most significant bits of x are kept, all lower bits are discarded. By doing that, the size of the ciphertext can be significantly decreased. Kyber compresses both ciphertext components (u, v), but to a different degree. The two compression parameters (d u , d v ) are specified in the parameter set.
Message encoding and decoding. For message encoding, i.e., mapping a message to an element in R q , Kyber follows the path of LPR and multiplies each message bit with q/2 . Recall that for decryption, a decoder is needed to recover the original message m from its noisy version m . This decoder is applied to each coefficient of m and returns 1 if the input value is in [q/4, 3q/4), and 0 otherwise. This must be done in a secure (read: constant time) manner, otherwise side-channel attackers might be able to infer information on m or s.
The decoding routine of Kyber's reference implementation 1 is sketched in Figure 3. First, it assures that all coefficients of the input polynomial a are in [0, q). Then, it loops over all coefficients (byte index i, bit index j). Decoding as such is then done in a single line of code, where all values are interpreted as unsigned integers. After multiplying the coefficient of the input a by 2 and adding q/2 , an integer division by q is performed. Note that compilers turn such divisions with constants into multiplications 2 , thereby avoiding typically non-constant-time division operations. Finally, the least-significant bit of the outcome gives the decoded message bit. To further illustrate this process, in Figure 4, we show how each of the above operations affects the probability distribution of the intermediate value (also cf. Figure 1). The multiplication by 2 scales the x axis, the following addition shifts the distributions to the right. The integer division by q leads to values between 0 and 2, picking the LSB then gives the correct decoded bit.

NewHope
NewHope [PAA + 19] is a key-encapsulation mechanism which bases its security on RLWE.
While it did not advance to the final round of the PQC process, it is still of significance, as it has already undergone some first real-world evaluations [Lan16,Inf17]. Just like Kyber, it uses an LPR-like public-key encryption scheme in combination with the FO described in Section 2.2 to construct a CCA-secure KEM. The NewHope NIST submission includes two parameter sets, with n = 512 and n = 1024, respectively. We give all other specified values in Table 3 of Appendix A.
Structure and differences. NewHope is, compared to Kyber, arguably a more direct successor to LPR due to it also being based on RLWE. Thus, it does not operate with matrices and vectors of polynomials. NewHope also employs ciphertext compression, but unlike Kyber, it only compresses v.
Message encoding and decoding routine. A distinguishing feature of NewHope is its message encoding routine. As encrypted messages are 256 bits long, whereas the used ring dimension n is much larger, it encodes each bit onto multiple coefficients and thereby increases resilience against decryption errors. Concretely, it repeats the message twice (for n = 512) or four times (for n = 1024) and then multiplies the coefficients of this extended message with q/2 . The decoding routine first applies the function flipabs(x) = |(x mod q) − q/2| to all coefficients. We show in Figure 5 how flipabs affects the coefficient-wise probability distribution of v − us; we also give its C code as included in NewHope's reference implementation 3 in Figure 6. The function coeff_freeze reduces the input x into the base interval [0, q). The subsequent subtraction sets r's sign bit if x < q/2. Recognize that r is declared as a signed integer. Thus, the following line performs an arithmetic shift by 15 positions. If r is positive (sign bit is 0), this shift flushes out all set bits and yields 0. Shifting a negative r (sign bit is 1) leads to all bits being set to 1, i.e., 0xffff, which equals −1 for an int16_t.
This property can be used in line 8. If m is zero, then both the addition and the XOR have no effect. If m is 0xffff= −1, all bits are flipped after subtracting 1. This is exactly the process of computing the two's complement. Thus, lines 7 and 8 perform a conditional negation and thereby compute the absolute value of r. After computing flipabs, the decoding routine sums up the 2 (NewHope512) or 4 (NewHope1024) coefficients encoding the same message bit. If this sum is larger than either q/2 (for n = 512 and two coefficients per message bits) or q (for n = 1024), then the decoder returns 1, and 0 otherwise. This comparison can be performed in constant time by subtracting q/2 (or q, respectively) and then returning the MSB.

Masked Decoder
The previously mentioned applicability of lattice-based schemes to embedded systems raises the need for adequate protection against side-channel attacks. Due to the linearity of many involved operations, e.g., polynomial addition and multiplication in R q , the masking countermeasure appears to be a perfect fit. Extending masking to the nonlinear decoder, however, is a much more involved task.
One possible way of building such a masked decoder was presented by Oder et al. [OSPG18], who describe a fully masked implementation of an LPR-like lattice KEM. Similar to NewHope, their custom KEM encodes each message bit onto multiple polynomial coefficients. The accompanying masked decoder is designed to handle this fact. As our first target is Kyber, we now describe the simpler version geared towards the single-coefficient-per-bit encoding scheme. Also, we use the Kyber parameter set, with q = 3329 and log 2 q = 12, for all further illustrations.
The decoding routine is illustrated in Figure 7. This figure again shows how each operation performed by the decoding algorithm affects the intermediate value's probability distribution. As all operations are performed in a modular domain (either modulo q or modulo a power of two), we adapt the circular representation of Oder et al. Note that the figure shows the distribution of the unmasked value, but all operations are performed in the masked domain. That is, the decoder is fed each coefficient m in masked form, i.e., the two shares m 1 and m 2 satisfy m = m 1 + m 2 in Z q . All subsequent operations are also done in a masked manner.
As a first step, the decoding routine subtracts q/4 from the input coefficient. Since this is a linear operation in Z q , it suffices to perform this subtraction on just one of the two shares. Then, the shares are transformed, from arithmetically mod q to arithmetically mod 2 bits , where bits = log 2 q + 1. For the details of this transform, we refer to the original paper [OSPG18]. After subtracting q/2 (mod 2 bits ) from one of the shares and performing a final arithmetic-to-boolean mask conversion, a masked representation of the decoded message bit can be retrieved by selecting the MSBs of the shares.

Previous Fault Attacks on Lattice-based KEMs
Thus far, the susceptibility of lattice-based KEMs against fault attacks is somewhat unexplored. Still, there exists some prior work.
Ravi et al.
[RRB + 19] propose a fault attack that can target key generation and encapsulation, but not decapsulation. They exploit the fact that long secrets are generated by expanding a short seed, which is additionally used multiple times but with a different domain separator. When injecting a fault such that the domain separator is reused, two values, such as s and e, are identical. Then, one can, e.g., trivially solve the equation b = as + e = (a + 1)s for the key s.
Valencia et al. [VOGR18] performed a more general study of the susceptibility of LPRlike encryption schemes against fault attacks. They show attacks that target decryption and can recover the secret key. However, their attacks are applicable only to CPA-secure systems, such as plain LPR. Their techniques cannot be applied to, e.g., Kyber and NewHope, as the FO transform would detect all their injected faults, and the resulting pseudorandom key is of no use in a differential fault attack. Also, their attacks require faulting multiple decryptions that use the same key. This must be avoided in systems providing only CPA security, as they could otherwise be easily broken with a chosenciphertext attack.
Thus, to the best of our knowledge, the susceptibility of FO-secured decapsulation has thus far not been properly investigated. We now change this in the following by presenting a new fault attack on broad range of lattice-based KEMs.

Generic Attack Description
In this section, we describe the underlying ideas and techniques of our attack. First, we describe the attacker's capabilities and discuss some trivial fault attacks, which we argue might either not be very realistic to mount or already obvious. Then, in Section 3.1, we observe that the decryption noise linearly depends on the secret polynomials e and s. In Section 3.2, we show that by injecting skipping faults in the decoder and then observing if the decapsulation still returns the correct shared secret (ineffective fault), one can restrict the possible values of the encryption noise and hence learn information on the long-term secrets. After repeating the above for many decapsulations, the attacker can create a linear system of inequalities, which we solve using a statistical method described in Section 3.3. Finally, we describe the efficient implementation of said statistical technique in Section 3.4.
Attacker model and steps. We assume that the adversary has the following capabilities and performs the now described basic steps. The attacker is in possession of the public key and can thus execute an arbitrary number of encapsulations. He gathers and stores not only the returned ciphertexts and shared secrets but also some intermediates computed during encapsulations, such as the sampled noise polynomials and the encrypted message. The attacker can filter the recorded encapsulation results according to some values known to him, e.g., the value of certain bits of the embedded encrypted message. However, he does not alter the ciphertexts, as the FO would always detect these modifications.
The adversary can then send a selected ciphertext to the target device, which holds the private key. He injects a specific skipping fault in PKE.Decrypt inside the decapsulation (cf. Figure 2), which is the only operation involving the private key s. Note, however, that the adversary cannot directly observe the decryption output µ . Instead, the attacker can only infer if the device still derived the correct shared secret (the fault was ineffective) or if the fault attack caused an incorrect decryption result (the fault was effective). This can be done by, e.g., decrypting a response from the target using the shared key returned by the corresponding encapsulation. If the resulting plaintext conforms to the used protocol, then the targeted device still computed the correct shared secret. If, however, the plaintext appears to be random, then the FO detected the fault and thus returned a random shared secret.
Simple attacks. Before describing our attack, we now discuss some very basic fault attacks against FO-secured KEMs and argue why these attacks might be impractical or already obvious.
First, an attacker might want to skip the equality check during decapsulation, i.e., whether c == c . This would then re-enable chosen-ciphertext attacks, such as shown in, e.g., [BGRR19]. However, fault injections might fail, and such attacks are typically not designed with uncertainties in mind. Also, we argue that the need to protect this obvious faulting target was already shown. In fact, skipping this check was previously proposed by Valencia et al. [VOGR18] in the context of their fault attacks. The need to protect the check was also noted by Oder et al. [OSPG18] and by Bauer et al. [BGRR19].
Another possible attack venue is exploiting ineffective faults in the stuck-at model [Cla07]. When an attacker can reliably fault an intermediate to a known value, e.g., to zero (stuckat-zero), and observes that the faulted device still returns the correct shared secret, he can deduce that the intermediate was already zero. Such a fault-enabled probing capability allows trivial key recovery when targeting intermediates having, e.g., a linear dependency on the coefficients of s. However, such stuck-at faults are not trivial to achieve in practice, especially on 32-bit devices. Also, due to the large range of possible values, e.g., Kyber's modulus is 3329, it might be unlikely that the targeted intermediate takes on the injected value. When also considering the large key sizes, a vast number of highly reliable fault injections might be needed for a successful attack.

On the Linearity of the Decryption Noise
Instead of using one of the above approaches, our attack exploits the key dependency of the encryption noise. Recall from Section 2.1 that m = v − us = er − e 1 s + e 2 + m q/2 , where we call d = er − e 1 s + e 2 the encryption noise. As noted above, we assume that the adversary (honestly) generated the ciphertexts. Hence, he knows all intermediate values computed during encapsulation, including e 1 , e 2 , and m. Now observe that the noisy plaintext m and thus also the decryption noise d are linear combinations of known values and the secrets e and s.
Also, note that all components of d have small coefficients. This ensures that d is always in the range of [−q/4, q/4]; else decryption errors would occur. 4 Thus, one can essentially ignore the modular reductions and interpret the equation of d to be in R = Z[x]/(x n + 1).
If an adversary somehow recovers the entire noise d (or m ) for two decryptions, then he can trivially solve the resulting system of linear equations for the unknowns e and s. A similar statement can be made for the much more realistic case where the attacker can only recover a single coefficient of d, but for many decryption queries. Here we can use the fact that polynomial multiplication in R q can be rewritten into a matrix-vector product. That is, for c = ab, we can also write c = Ab, where, with a slight abuse of notation, we equate polynomials with their coefficient vectors. The i-th column of A can be generated by computing a · x i in R q . This matrix-vector representation now allows to extract the computation of each individual coefficient of c. Concretely, we write c[i] = a (i) , b , where a (i) is the i-th row of A and ·, · denotes an inner product. For the reduction polynomial x n + 1 used in LPR, this equates to  of e and s). Gathering 2n of these equations again allows for key recovery using linear algebra. This technique of extracting single linear equations over many calls and then solving the entire system was already shown to be useful for side-channel attacks on lattice-based schemes [GBHLY16].

Fault Injection in Decoding
With a fault attack, it is not trivial to recover the true value of any d [i]. Thus, we instead aim at using a relatively simple fault to acquire a hint on its value. Concretely, we inject a skipping fault in the decoder and then use the observed decapsulation outcome, i.e., whether the injected fault was effective or ineffective, as an oracle for d [i]. We now explain this approach on the example of Kyber's decoding routine described in Section 2.3. We attack the decoding routine for one selected coefficient, e.g., for m[i], and inject a fault such that the addition of q/2 (the second step in the visualization given in Figure 4) is skipped. Figure 8 now shows how this skipping fault influences the decoding process. Note that if the encryption noise d ≥ 0, which corresponds to the right side of the distributions, then the correct value is still recovered. This is the case no matter the value of the encoded bit. Hence, the fault injection was ineffective. If, however, d < 0, then the faulted decoding returns an incorrect result; the fault is effective.
Thus, by injecting this skipping fault and then testing whether the attacked device still derives the correct key, we can infer if d[i] is positive or negative. More formally, we have: For now, we assume that our skipping fault has perfect reliability. We explain methods to deal with unreliable faults in Section 6.

Solving a System of Linear Inequalities
Each such equation gives a small amount of information on e and s. Thus, the adversary has to fault many decapsulations, where he can set up one equation per faulted execution. When using r (ij ) j to denote the value of r (i) in the j-th decapsulation, and gathering a total of m equations, we can write: The index i j of the targeted coefficient can be different for each fault injection and thus each line in the system. We introduce dedicated symbols for the above system: we call the left matrix X, y = (e||s), and the right-hand side of the equation z. The attacker now wants to find the single y satisfying all these constraints. We note that similar problems need to be solved for attacks exploiting decryption errors, e.g., [DGJ + 19]. When encountering or enforcing such an error, one can infer that |d| ≥ q/4 and use this information to construct a somewhat similar set of constraints.
Such a system of inequalities cannot be solved using straight-forward linear algebra. An approach that appears to be promising instead is linear programming (LP) since LP solvers already deal with such linear constraints. However, we found that the runtime of LP solvers grew very fast with the problem dimension, so much so that the required dimensions of more than 1000 unknowns appear to be out of reach. Also, LP solvers require hard constraints. However, fault injection might sometimes fail, which can then be mistaken as an ineffective fault. A single resulting erroneous inequality might already be enough to eliminate the correct solution. Hence, a more resilient approach is needed.
We now describe a statistical approach that can deal with the large dimension and is (somewhat) error-tolerant. For each of the 2n secret coefficients, we store a vector of length |χ| containing the probabilities for all its values (all key guesses). These vectors are initialized with the probabilities given by the error distribution χ. We then use an iterated method to update said probabilities given all constraints.
Assume Performing this computation once for all coefficients, however, did not yield satisfactory results. For this reason, we repeat this entire process with the now updated probability vectors. After each such iteration, we pick the n most likely key values, which can then be plugged into the key relation b = as + e. The resulting linear system with n unknowns and n equations can be solved to recover the remaining n unknowns, given that the first n recovered coefficients are correct. We keep iterating the entire above process until either the correct key is recovered, or a defined maximum number of iterations-we set this threshold to 10-is reached.
We note that the described algorithm is related to the belief-propagation technique, which can be used for a plethora of inference tasks. It has seen some prior use in the context of side-channel analysis [VGS14], including attacks on lattice-based schemes [PPM17,PP19].
We also mention that the algorithm is not limited to working with inequalities, but can be adapted to exploit any information on d [i]. For instance, faults in other locations followed by the distinction between effective and ineffective faults might instead reveal the LSB of d[i], or that |d[i]| is within a certain range. Such information can also be incorporated.

Efficient Attack Implementation
The above is a relatively high-level description of our key-recovery algorithm. We now describe some steps required to make the recovery process practical.
Clustering. First, we decrease the dimension of the system by clustering multiple unknowns into single variables. The cluster sizes are chosen such that the number of key guesses can still be manageable given the runtime and memory constraints. In Kyber, for instance, the error polynomials are sampled from the centered binomial distribution over the range [−2, 2], giving us 5 possible values per coefficient. We chose to cluster 4 coefficients, giving us 5 4 = 625 key guesses per cluster. Additionally, after each iteration of our algorithm, we discard key guesses having very low probability and then merge clusters such that their combined size is again enumerable. For ease of understanding, we do not consider clustering in the following explanations, but remember that it is still used.

Efficient summation of probability distributions.
A major runtime hurdle in the above algorithm is the computation of the probability distribution of j=0...2n−1\i X[k, j]y [j] for all equations k and secret coefficients i. A naive summation is prohibitively expensive, which is why we use the following optimization.
When given two discrete random variables A, B and their respective distributions as a vector of probabilities, the probability distribution of C = A + B can be computed by convolving the probability vectors of A and B. This convolution can be efficiently computed by utilizing the FFT and performing a pointwise multiplication of the transformed distributions. Thus, we compute FFT(Pr(X[k, j]y[j])), where the probability vector first has to be zero-padded such that it can deal with the full expected range of d. Then, the pointwise product over the transformed vectors for all j = 0 . . . 2n − 1\i entries, followed by an inverse FFT, leads to the probability vector of the j=0...2n−1\i X[k, j]y[j].
Minimizing recomputations. The above needs to be computed for all coefficients i. Doing that via a simple loop over i would entail lots of recomputation of partial pointwise products. As an illustration, observe that products for two different i differ only by a single factor. We use dynamic programming to reuse such common factors. We store partial products in a binary tree, where the 2n leaves are initialized to FFT(Pr(X[k, j]y[j])). We then move towards the root; for each node, we multiply the partial products of its children. We call these partial products the upward distributions.
After processing all nodes, we begin moving towards the leaves again and compute the downward distributions. In the layer below the root, the downward distributions are computed by multiplying the upward distributions of all respective siblings. For the next layers, the downward distribution is obtained by combining the downward distribution of the parent with the upward distribution of the siblings. Thus, for each node, the downward distribution describes the sum of all leaves that are not below the node. After fully traversing the tree in this manner, the required distributions are the downward messages of the leaves.
By using this method, the runtime complexity can be reduced from O(n 2 ) (simple loop over i) to O(n), at the cost of higher memory requirements.

Application to Kyber and NewHope
The previous section gave a somewhat generic description and targeted a combination of plain LPR with the FO. We now describe the steps needed to apply our attack on concrete schemes and their decoder implementations. We start with Kyber in Section 4.1, then discuss how the attack can be applied on a masked Kyber implementation in Section 4.2, and finally, in Section 4.3, show that other LPR-like schemes, concretely NewHope, can also be susceptible.

Kyber
The previous section explained the generic attack on Kyber's decoder but still targeted plain LPR. Some additional steps are needed to actually apply our attack to Kyber.
Recall that Kyber compresses both ciphertext components u and v via rounding, i.e., by, in simplified words, dropping the low order bits (cf. Section 2.3). This compression needs to be accounted for when setting up our system of inequalities. We write u = u + ∆u and v = v + ∆v, where u, v are the uncompressed terms, u and v is the compressed ciphertext, and ∆u, ∆v denotes the additive rounding error. We note that in our attack scneario, the adversary performs the encapsulation and thus knows the uncompressed value and the rounding error.
When now performing back substitution in v − u s = (v + ∆v) − (u + ∆u)s, similar to Equation (1), we arrive at: m = m · q 2 + er + e 2 + ∆v − (e 1 + ∆u)s and thus have d = er −(e 1 +∆u)s+e 2 +∆v. The value of ∆v can be somewhat large. Since our fault attack probes the sign of d, some inequalities will thus be fulfilled by (almost) all values of e and s. We thus filter for small |e 2 + ∆v|, i.e., we only send those ciphertexts to the target where during encapsulation, this value was observed to be within some bound. Concretely, we only use the ciphertext of encapsulations where |e 2 + ∆v| ≤ 10. All other steps of the attack are performed as described in the previous section.

Kyber using the Masked Decoder
While masking is a powerful countermeasure against various side-channel attacks, it is, at least in general, not effective in protecting against faults. However, our attack probes the value of the (implicit) intermediate d, which only appears in masked form in a protected implementation. Hence, it might appear that side-channel protections, which are required anyway in a vulnerable environment, already thwart our attack. We now show that this is not the case. While we do not claim that all masked implementations are susceptible, we demonstrate that masking as such does not hamper our attack. We do so by adapting the attack to the masked decoder of Oder et al. [OSPG18], which we introduced in Section 2.5.
Recall that the first step of this decoder is to subtract q/4 (mod q) and that the input to the decoder is arithmetically shared over Z q . As this subtraction is a linear operation in Z q , it suffices to perform it on just one of the two shares. The effects of skipping this subtraction are shown in Figure 9. The transformation to arithmetic shares mod 2 bits now splits the distribution for a 1-bit into two parts. The final subtraction of q/2 shifts the distributions such that no decoding error occurs when d ≥ 0 (marked in green), but the wrong value is returned when d < 0 (marked in red). Thus, we observe the exact same effect as in the unmasked case. Hence, the next attack steps are identical. Figure 9: Visualization of the effect of skipping the first subtraction in the masked decoder of Oder et al. [OSPG18]

NewHope
Recall from Section 2.4 that NewHope encodes each message bit onto multiple coefficients. For decoding, first the flipabs function is run on all n coefficients of m . Then, the 2 (for n = 512) coefficients encoding the same message bit are added. Finally, after subtracting q/2, the sign bit is returned. We found that skipping a particular instruction in one call to the flipabs routine again allows us to learn the sign of d. Concretely, we skip the XOR with the bitmask m (line 8 of Figure 6). We now discuss the exact effect of this fault via a case study.
If the input x ≥ q/2, i.e., x is on the right half of Figure 1b, then r is positive and m = 0. XORing a value of 0 has already no effect. Thus, the instruction skip is always ineffective, and the correct value is still returned.
If x < q/2, then r < 0 and m = 0xffff, which equals −1 for the int16_t data type. Skipping the XOR thus results in returning x − q/2 − 1 instead of the desired value |x − q/2|. This incorrect value is now added to the outcome of flipabs of the second coefficient encoding the same bit. We dub x 1 the result of the faulted flipabs call and x 2 the returned value of the undisturbed call, where x 2 follows the distribution shown in the right half of Figure 5. If the encoded message bit is 0, then we have x 1 ∈ [−q/2 − 1, q/4 − 1] and x 2 ∈ [q/4, q/2). The sum of these values is in [−q/4 − 1, q/4 − 1), which is always smaller than q/2 and will thus incorrectly decode to a 1. If the original message bit is 1, then x 1 ∈ [−q/4, −1] and x 2 ∈ [0, q/4], which leads to a sum in [−q/4, q/4). This will again be decoded to a 1, which is the correct value in this case.
For a message bit with value 0, d ≥ 0 will thus lead to an ineffective fault, whereas d < 0 leads to corrupted result. Hence, we again set up a system of linear inequalities and solve for the key. For a message bit with value 1, the injected fault is always ineffective; the returned value is correct regardless of the value of d. We thus only send ciphertexts to the target where the attacked coefficient encodes a 0. The attacker cannot directly control the encrypted message, as it is generated by hashing a seed. However, the attacker can just discard seeds that lead to a 1 in the targeted position.
Compression. Unlike Kyber, NewHope only compresses the second ciphertext component v. We again filter for ciphertexts where |∆v + e 2 | is small.

Evaluation
In this section, we put the previous descriptions into practice and evaluate the performance of our attack. Using fault simulations, we analyze how many faulted decapsulations are needed for key recovery. We also investigate the computational-resource requirements for solving the system of inequalities with our algorithm. Implementation. We implemented the statistical solving approach described in Section 3.3, including all optimizations mentioned in Section 3.4, in Matlab. All source code is available at https://github.com/latticekemfaults/latticekemfaults/.
For all evaluations presented in this section, we used fault simulations. That is, we modified the decapsulation of the Kyber and NewHope reference implementations such that the desired skipping fault is done in software. Thus, these evaluations assume perfect faulting reliability. However, we analyze a scenario with unreliable faults in Section 6. We analyzed all proposed Kyber parameter sets (Kyber512, Kyber768, and Kyber1024), and the smaller NewHope parametrization (NewHope512).

Number of Fault Injections
Each injected fault allows us to set up a linear inequality that carries a small amount of information on the long-term secret key. We now analyze how many such inequalities and thus fault injections are needed for full key recovery.
We performed a sweep over the number of inequalities for each mentioned parameter set. For each analyzed quantity, we perform 20 experiments and determine the success rate. The outcome for Kyber is shown in Figure 10. For the smallest parameter set, namely Kyber512, one needs approximately 6,500 fault injections to achieve a success rate above 90%. As to be expected, this number grows significantly for Kyber768 and Kyber1024. To achieve a similar success rate, we need 9,500 and 13,000 faults, respectively. The result for NewHope512 is shown in Figure 11. Compared to Kyber512, attacking NewHope512 requires a much larger number of faults, despite being in the same NIST security category. We can attribute this, at least in part, to the larger key space. In Kyber, key coefficients are drawn from a centered binomial distribution over [−2, 2], but in NewHope, they are sampled from [−8, 8]. We were not able to attack NewHope1024, potentially due to these reasons.

Resource Requirements
Key recovery requires solving a very large system with at least 1024 unknowns and around 10,000 inequalities. Additionally, the algorithm does not assign a single value to the unknowns but instead needs to keep track of their entire probability distribution. Thus, the resource use of the solving algorithm is non-negligible.
The runtime and memory consumption depends on the size of the system, i.e., on both the number of unknowns and on the number of inequalities. The former is prescribed by the targeted parameter set. In Kyber, we have 2kn unknowns, which translates to 1024 for Kyber512. Successful attacks required at least 5,500 inequalities, but we used up to 18,000 during evaluations.
We give some exemplary resource requirements in Table 1. For each parameter set, we measured the runtime and memory requirements for one selected number of faults. We always picked the lowest number where the success rate, as per the analysis shown in Section 5.1, is at least 90%. All these measurements were done using 8 cores of a Xeon E5-4669 v4 2.2 GHz. The average runtime ranges between 3 and 20 minutes. Memory might be more of a limiting factor, as we required up to 79 GB of RAM. However, we did not particularly optimize our implementation in this regard, as our testing machine did still provide more than enough memory.

Experimental Verification on an M4
The above experiments use simulations to show that a single skipping fault per decapsulation can indeed be enough for key recovery. To demonstrate that the attack is also practical, we successfully attacked Kyber512 running on an ARM-based microcontroller. This section describes the experiment and discusses its outcome.

Setup
For our experiment, we targeted an STM32F405 microcontroller featuring an ARM Cortex M4 core. The Cortex M4, and the STM32F40X series in particular, is the de-facto standard platform for evaluating embedded software implementations of schemes running in NIST's PQC process.
Our target device is mounted on the ChipWhisperer UFO board [Newb], which allows for relatively simple fault injection. Concretely, we use a ChipWhisperer Lite board [Newa] to generate the 24 MHz base clock, which the target device then directly uses as its core clock. We added a trigger signal to mark the beginning of the decoding process. We then inject a clock glitch such that a single chosen instruction is skipped, as described in the previous section. Determining the exact glitching parameters and the timing of the targeted instruction was done using sweeps over the glitching parameter space on an extracted implementation of the decoder.
We run the unprotected and in large parts assembly-optimized Kyber512-90s implementation included in the PQM4 library [KRSS]; the C portion of the code is compiled using the O3 optimization level. The 90s version of Kyber replaces calls to Keccak with SHA2 and AES. We use this version simply because it runs slightly faster on our target. Apart from this, the choice of the used symmetric primitives does not affect our attack. We note that decoding is not manually optimized and instead uses the C code from the Kyber reference implementation. Still, as our attack requires only a single instruction skip, we do not expect worse attack performance when using an assembly-optimized routine. 5

Attack Steps
We run encapsulation on a PC, which received the public key directly from the device. The PC can perform an arbitrary number of encapsulations and then decide which out of the generated ciphertexts to send to the device. As stated in Section 4.1, we only use the outcome of encapsulations where |e 2 + ∆v| ≤ 10, all other ciphertexts are discarded.
After sending such a selected ciphertext to the target device, it runs decapsulation, during which the described skipping fault is injected. For the sake of simplicity, the device directly replies with the computed shared secret key in clear. Thus, the attacker can directly test whether the received key matches the output of encapsulation (fault was ineffective) or if they differ (fault was effective). We note that in a real-world attack, the adversary does not directly receive the shared key, but can, e.g., decrypt follow-up messages with the shared secret and test whether they adhere to the used protocol (correct shared key) or if they appear to be random garbage (incorrect shared key).
Dealing with unreliable injections. The described attack needs to distinguish between effective and ineffective fault injections. However, failed fault injections, i.e., cases where no instruction is actually skipped, cannot be distinguished from ineffective faults by just observing the shared secret. With our inexpensive setup, we were not able to achieve a high enough reliability for fault injection. Without further filtering, the attack failed due to the large number of incorrect inequalities. For this reason, we only use data from decapsulations returning an incorrect shared secret. In these cases, we can be certain that the fault injection worked and that the fault was effective. As we expect that about half the injected faults are ineffective, we thus have to discard the data from at least half of the faulted decapsulation queries.
Despite this filtering, some of the generated inequalities turned out to be incorrect. This can be the case when the injected clock glitch has some other (unknown) effect, such as general data corruption or skipping a different instruction. We call this scenario unintended faults. When assuming that the decoder returns a random bit in such a case, then unintended faults will be misclassified in about 50% of all injections. This percentage likely differs for a real setup, as the outcome of unintended faults can still show a bias. As it turns out, the statistical solution approach presented in Section 3.3 can deal with some incorrect inequalities without further adaptations. We discuss potential methods to achieve a higher robustness against unintended faults in Section 7.

Results
We ran 6 key recovery experiments, each one using a different key. For each experiment, we gathered 10,000 linear inequalities. With perfect faulting reliability, this would also be the number of required fault injections. As we filter for effective faults, we need to double that number. However, with our inexpensive setup, we did not achieve a very high faulting reliability. Some injections lead to crashing the device, while many others resulted in the correct shared key. As explained above, we need to discard such trials.
In 5 out of the 6 experiments, approximately 17% of the faulted decapsulations were exploitable and allowed the extraction of a linear inequality, 6 for the sixth run this number dipped to 8%. This corresponds to faulting roughly 60,000 and 125,000 decapsulations and required about 8.5 hours and 16 hours, respectively.
When feeding the gathered system of inequalities into our key-recovery algorithm, the correct private key was always successfully recovered. After plugging the recovered private key back into the inequalities, we found that between 0.4% and 1% of them were incorrect, presumably due to unintended faults. Still, this shows that the recovery algorithm is somewhat resilient against such errors.
As our goal was to demonstrate the feasibility of the attack, and as instruction skips are a well-established fault model and have been shown to work in the past, we did not put further effort into improving the above numbers. Still, we note that a determined adversary using more sophisticated faulting equipment can likely cut down the number of faulted decapsulations, ideally to the fault quantities found using simulations, and thereby drastically reduce the attack time.

Robustness against erroneous inequalities.
To get a better grasp on the robustness of our approach, we ran additional simulations with the above settings (Kyber512, 10,000 faults) and artificially introduced errors in the inequalities. With an error rate of 0.5%, the success rate is roughly 70%. When 1% of the inequalities are incorrect, the success rate drops into single-digit percentages. Since all practical experiments succeeded, we believe that the occurred errors still have some bias. We describe a method to deal with higher error rates in the following section.

Countermeasures and Future Work
While the FO inherently prevents many kinds of fault attacks, the presented method clearly shows that practical attacks are still possible. Our attack requires a single instruction skip per decapsulation and also shows resilience against erroneous fault injections. Thus, countermeasures are still needed. We now discuss several options and then conclude with possible future work.

Countermeasures
Protocol-level countermeasures. Our attack requires that the targeted device decapsulates any attacker-generated ciphertexts. Thus, if either the public key is only known to trusted parties or the target only runs decapsulation for ciphertexts signed by such a trusted party, the attack is prohibited. However, this might not be possible or practical in many applications.

Redundancy.
Arguably the most popular method to protect against faults is to introduce redundancy and use it for error detection. The FO provides such redundancy through the involved re-encryption, but as shown, it does not prevent the attack.
The simplest form of redundancy is course-grained double execution, i.e., to run decapsulation twice and only return the shared secret if both results are equal. However, our attack does not require knowing the (faulty) shared secret; we only need to detect whether the injected fault changed the outcome. This is still possible with double execution in place, and possibly even easier if the device reacts differently upon detecting a fault.
Still, double execution can also be applied on a finer granularity. By using double computation to validate the integrity of the intermediates within the decoder, some instances of our attack can be prevented. For the attack on Kyber, for instance, we skip the addition of a constant. This will always be detected, no matter if the fault would change the outcome of the decoder. However, in the attack on NewHope described in Section 4.3, we skip the XOR with the bitmask m. For a message bit 0 and d ≥ 0, m has a value of 0. As the XOR does not change any values in this case, the skipping fault is not detected, meaning it is still possible to differentiate between effective and ineffective faults.
Some lattice-based KEMs apply an error-correction code to the plaintext m and then run a decoder on the recovered plaintext. While this is done to increase the resilience against decryption errors, this also severely impedes our attack. Determining if our attack can be adapted to this setting would need further study.

CFI.
A generic countermeasure that will always detect our attack is (fine-grained) controlflow integrity. We rely on skipping faults. Thus, an implementation which can ensure that the sequence of executed instructions is correct will not be vulnerable.
Shuffling. Finally, one very effective and easy to implement countermeasure appears to be shuffling. For setting up a linear inequality, we need to know which coefficient index i we faulted. Since the decoder is called for each coefficient independently, the order in which the coefficients are processed can easily be shuffled. While an attacker can still target the decoder and even differentiate between effective and ineffective faults, the uncertainty on i prevents deriving the inequality and thus hinders the attack. As an additional bonus, this shuffling countermeasure also hampers side-channel attacks.

Future Work
Improving the robustness. For scenarios where the algorithm fails due to unintended faults, it can be adapted to cope with the larger error rates. One can estimate the expected error rate and incorporate this probability in the Bayesian update step. While this will inevitably increase the number of required fault injections, it will make the approach more robust.
Adaptation to other schemes. While we concretely apply the attack on the reference implementations of Kyber and NewHope, our descriptions of Section 3 target FO-protected plain LPR. Thus, many more LPR-based schemes (and their implementations) might be vulnerable against similar attacks. We now discuss some of these schemes.
• Saber [DKRV19] is a third-round finalist and thus a direct competitor to Kyber.
Unlike Kyber and NewHope, it bases its security on the Learning with Rounding problem (LWR). For, e.g., key generation, it samples a random s and then generates the public key b = as . That is, it does not sample a random e, but instead generates an error by rounding the product. Still, the above can be rewritten as b = as + e, with e = as − as. Another differentiating feature is its use of a power-of-two modulus instead of a prime. Still, as it is structurally very similar to Kyber, and as the error due to rounding can be made explicit, our attack might be applicable.
• Frodo [NAB + 19], which advanced to the third round as an alternate candidate, uses an unstructured lattice and encodes multiple message bits into each coefficient. We did not study the susceptibility of this approach.
• NTRU Prime [BCLvV19], also an alternate candidate in the third round, includes a variant NTRU LPrime, which, as the name already implies, can also be seen as being based on LPR. Hence, this variant might also be susceptible.
• LAC [LLJ + 19] and Round5 [GMZB + 19], both second-round candidates in NIST's PQC process, employ error correction codes on the encrypted plaintext. As stated earlier, this will severely impede our attack. Still, we do not rule out that the attack can be adapted to this setting.
Incorporating lattice reduction. Our statistical algorithm returns probabilities for each coefficient of the secret key s and the error vector e. Thus far, we simply picked the n coefficients with the highest confidence and then solved the linear system b = as + e. A small number of errors in the recovered coefficients can be corrected by enumerating likely error positions. Alternatively, one can recover less than n coefficients, plug these into b = as + e, and then perform key recovery using lattice basis reduction. This requires a hard classification, i.e., information on the confidence cannot be further incorporated.
Recently, Dachman-Soled et al. [DDGR20] showed how such probabilities (soft information) can be incorporated into a lattice-reduction approach. There, however, it is important that the probabilities are somewhat reliable. We found that if our algorithm cannot recover the key, then it latches onto the most likely values and boosts their probability close to 1. We suspect that this is due to a positive feedback loop, i.e., the probability vector of a coefficient influences itself after at least two iterations. A possible solution is to abort our algorithm after a lower number of iterations, i.e., before the positive feedback has too much of an adverse effect.