Akira KITAYAMA Goichi ONO Hiroaki ITO
Edge devices with strict safety and reliability requirements, such as autonomous driving cars, industrial robots, and drones, necessitate software verification on such devices before operation. The human cost and time required for this analysis constitute a barrier in the cycle of software development and updating. In particular, the final verification at the edge device should at least strictly confirm that the updated software is not degraded from the current it. Since the edge device does not have the correct data, it is necessary for a human to judge whether the difference between the updated software and the operating it is due to degradation or improvement. Therefore, this verification is very costly. This paper proposes a novel automated method for efficient verification on edge devices of an object detection AI, which has found practical use in various applications. In the proposed method, a target object existence detector (TOED) (a simple binary classifier) judges whether an object in the recognition target class exists in the region of a prediction difference between the AI’s operating and updated versions. Using the results of this TOED judgement and the predicted difference, an automated verification system for the updated AI was constructed. TOED was designed as a simple binary classifier with four convolutional layers, and the accuracy of object existence judgment was evaluated for the difference between the predictions of the YOLOv5 L and X models using the Cityscapes dataset. The results showed judgement with more than 99.5% accuracy and 8.6% over detection, thus indicating that a verification system adopting this method would be more efficient than simple analysis of the prediction differences.
Kazuki SUNAGA Takeya YAMADA Hiroki MATSUTANI
A practical issue of edge AI systems is that data distributions of trained dataset and deployed environment may differ due to noise and environmental changes over time. Such a phenomenon is known as a concept drift, and this gap degrades the performance of edge AI systems and may introduce system failures. To address this gap, retraining of neural network models triggered by concept drift detection is a practical approach. However, since available compute resources are strictly limited in edge devices, in this paper we propose a fully sequential concept drift detection method in cooperation with an on-device sequential learning technique of neural networks. In this case, both the neural network retraining and the proposed concept drift detection are done only by sequential computation to reduce computation cost and memory utilization. We use three datasets for experiments and compare the proposed approach with existing batch-based detection methods. It is also compared with a DNN-based approach without concept drift detection. The evaluation results of the proposed approach show that the proposed method is capable of detecting each of four concept drift types. The results also show that, while the accuracy is decreased by up to 0.9% compared to the existing batch-based detection methods, it decreases the memory size by 88.9%-96.4% and the execution time by 45.0%-87.6%. As a result, the combination of the neural network retraining and the proposed concept drift detection method is demonstrated on Raspberry Pi Pico that has 264 kB memory.
Kyosuke YAMASHITA Keisuke HARA Yohei WATANABE Naoto YANAI Junji SHIKATA
This paper considers the problem of balancing traceability and anonymity in designated verifier signatures (DVS), which are a kind of group-oriented signatures. That is, we propose claimable designated verifier signatures (CDVS), where a signer is able to claim that he/she indeed created a signature later. Ordinal DVS does not provide any traceability, which could indicate too strong anonymity. Thus, adding claimability, which can be seen as a sort of traceability, moderates anonymity. We demonstrate two generic constructions of CDVS from (i) ring signatures, (non-ring) signatures, pseudorandom function, and commitment scheme, and (ii) claimable ring signatures (by Park and Sealfon, CRYPTO'19).
Nabilah SHABRINA Dongju LI Tsuyoshi ISSHIKI
The fingerprint verification system is widely used in mobile devices because of fingerprint's distinctive features and ease of capture. Typically, mobile devices utilize small sensors, which have limited area, to capture fingerprint. Meanwhile, conventional fingerprint feature extraction methods need detailed fingerprint information, which is unsuitable for those small sensors. This paper proposes a novel fingerprint verification method for small area sensors based on deep learning. A systematic method combines deep convolutional neural network (DCNN) in a Siamese network for feature extraction and XGBoost for fingerprint similarity training. In addition, a padding technique also introduced to avoid wraparound error problem. Experimental results show that the method achieves an improved accuracy of 66.6% and 22.6% in the FingerPassDB7 and FVC2006DB1B dataset, respectively, compared to the existing methods.
Yingyao WANG Han WANG Chaoqun DUAN Tiejun ZHAO
Question-answering tasks over structured knowledge (i.e., tables and graphs) require the ability to encode structural information. Traditional pre-trained language models trained on linear-chain natural language cannot be directly applied to encode tables and graphs. The existing methods adopt the pre-trained models in such tasks by flattening structured knowledge into sequences. However, the serialization operation will lead to the loss of the structural information of knowledge. To better employ pre-trained transformers for structured knowledge representation, we propose a novel structure-aware transformer (SATrans) that injects the local-to-global structural information of the knowledge into the mask of the different self-attention layers. Specifically, in the lower self-attention layers, SATrans focus on the local structural information of each knowledge token to learn a more robust representation of it. In the upper self-attention layers, SATrans further injects the global information of the structured knowledge to integrate the information among knowledge tokens. In this way, the SATrans can effectively learn the semantic representation and structural information from the knowledge sequence and the attention mask, respectively. We evaluate SATrans on the table fact verification task and the knowledge base question-answering task. Furthermore, we explore two methods to combine symbolic and linguistic reasoning for these tasks to solve the problem that the pre-trained models lack symbolic reasoning ability. The experiment results reveal that the methods consistently outperform strong baselines on the two benchmarks.
Hiroki YAMAMURO Keisuke HARA Masayuki TEZUKA Yusuke YOSHIDA Keisuke TANAKA
Message franking is introduced by Facebook in end-to-end encrypted messaging services. It allows to produce verifiable reports of malicious messages by including cryptographic proofs, called reporting tags, generated by Facebook. Recently, Grubbs et al. (CRYPTO'17) proceeded with the formal study of message franking and introduced committing authenticated encryption with associated data (CAEAD) as a core primitive for obtaining message franking. In this work, we aim to enhance the security of message franking and introduce forward security and updates of reporting tags for message franking. Forward security guarantees the security associated with the past keys even if the current keys are exposed and updates of reporting tags allow for reporting malicious messages after keys are updated. To this end, we firstly propose the notion of key-evolving message franking with updatable reporting tags including additional key and reporting tag update algorithms. Then, we formalize five security requirements: confidentiality, ciphertext integrity, unforgeability, receiver binding, and sender binding. Finally, we show a construction of forward secure message franking with updatable reporting tags based on CAEAD, forward secure pseudorandom generator, and updatable message authentication code.
Yutaka MASUDA Yusei HONDA Tohru ISHIHARA
Approximate computing (AC) has recently emerged as a promising approach to the energy-efficient design of digital systems. For realizing the practical AC design, we need to verify whether the designed circuit can operate correctly under various operating conditions. Namely, the verification needs to efficiently find fatal logic errors or timing errors that violate the constraint of computational quality. This work focuses on the verification where the computational results can be observed, the computational quality can be calculated from computational results, and the constraint of computational quality is given and defined as the constraint which is set to the computational quality of designed AC circuit with given workloads. Then, this paper proposes a novel dynamic verification framework of the AC circuit. The key idea of the proposed framework is to incorporate a quality assessment capability into the Coverage-based Grey-box Fuzzing (CGF). CGF is one of the most promising techniques in the research field of software security testing. By repeating (1) mutation of test patterns, (2) execution of the program under test (PUT), and (3) aggregation of coverage information and feedback to the next test pattern generation, CGF can explore the verification space quickly and automatically. On the other hand, CGF originally cannot consider the computational quality by itself. For overcoming this quality unawareness in CGF, the proposed framework additionally embeds the Design Under Verification (DUV) component into the calculation part of computational quality. Thanks to the DUV integration, the proposed framework realizes the quality-aware feedback loop in CGF and thus quickly enhances the verification coverage for test patterns that violate the quality constraint. In this work, we quantitatively compared the verification coverage of the approximate arithmetic circuits between the proposed framework and the random test. In a case study of an approximate multiply-accumulate (MAC) unit, we experimentally confirmed that the proposed framework achieved 3.85 to 10.36 times higher coverage than the random test.
Recently, Linux Container has been the de-facto standard for a cloud system, enabling cloud providers to create a virtual environment in a much more scaled manner. However, configuring container networks remains immature and requires automatic verification for efficient cloud management. We propose Verikube, which utilizes a novel graph structure representing policies to reduce memory consumption and accelerate verification. Moreover, unlike existing works, Verikube is compatible with the complex semantics of Cilium Policy which a cloud adopts from its advantage of performance. Our evaluation results show that Verikube performs at least seven times better for memory efficiency, at least 1.5 times faster for data structure management, and 20K times better for verification.
Takashi TOMITA Shigeki HAGIHARA Masaya SHIMAKAWA Naoki YONEZAKI
This paper focuses on verification for reactive system specifications. A reactive system is an open system that continuously interacts with an uncontrollable external environment, and it must often be highly safe and reliable. However, realizability checking for a given specification is very costly, so we need effective methods to detect and analyze defects in unrealizable specifications to refine them efficiently. We introduce a systematic characterization on necessary conditions of realizability. This characterization is based on quantifications for inputs and outputs in early and late behaviors and reveals four essential aspects of realizability: exhaustivity, strategizability, preservability and stability. Additionally, the characterization derives new necessary conditions, which enable us to classify unrealizable specifications systematically and hierarchically.
Hiro TAMURA Kiyoshi YANAGISAWA Atsushi SHIRANE Kenichi OKADA
This paper presents a physical layer wireless device identification method that uses a convolutional neural network (CNN) operating on a quadrant IQ transition image. This work introduces classification and detection tasks in one process. The proposed method can identify IoT wireless devices by exploiting their RF fingerprints, a technology to identify wireless devices by using unique variations in analog signals. We propose a quadrant IQ image technique to reduce the size of CNN while maintaining accuracy. The CNN utilizes the IQ transition image, which image processing cut out into four-part. An over-the-air experiment is performed on six Zigbee wireless devices to confirm the proposed identification method's validity. The measurement results demonstrate that the proposed method can achieve 99% accuracy with the light-weight CNN model with 36,500 weight parameters in serial use and 146,000 in parallel use. Furthermore, the proposed threshold algorithm can verify the authenticity using one classifier and achieved 80% accuracy for further secured wireless communication. This work also introduces the identification of expanded signals with SNR between 10 to 30dB. As a result, at SNR values above 20dB, the proposals achieve classification and detection accuracies of 87% and 80%, respectively.
Smart contracts are protocols that can automatically execute a transaction including an electronic contract when a condition is satisfied without a trusted third party. In a representative use-case, a smart contract is executed when multiple parties fairly trade on a blockchain asset. On blockchain systems, a smart contract can be regarded as a system participant, responding to the information received, receiving and storing values, and sending information and values outwards. Also, a smart contract can temporarily keep assets, and always perform operations in accordance with prior rules. Many cryptocurrencies have implemented smart contracts. At POST2018, Atzei et al. give formulations of seven fair exchange protocols using smart contract on Bitcoin: oracle, escrow, intermediated payment, timed commitment, micropayment channels, fair lotteries, and contingent payment. However, they only give an informal discussion on security. In this paper, we verify the fairness of their seven protocols by using the formal verification tool ProVerif. As a result, we show that five protocols (the oracle, intermediated payment, timed commitment, micropayment channels and fair lotteries protocols) satisfy fairness, which were not proved formally. Also, we re-find known attacks to break fairness of two protocols (the escrow and contingent payment protocols). For the escrow protocol, we formalize the two-party scheme and the three-party scheme with an arbitrator, and show that the two-party scheme does not satisfy fairness as Atzei et al. showed. For the contingent payment protocol, we formalize the protocol with the non-interactive zero-knowledge proof (NIZK), and re-find the attack shown by Campanelli et al. at CCS 2017. Also, we show that a countermeasure with subversion NIZK against the attack works properly while it is not formally proved.
Tong ZHANG Yujue WANG Yong DING Qianhong WU Hai LIANG Huiyong WANG
With the development of Internet technology, the demand for signing electronic contracts has been greatly increased. The electronic contract generated by the participants in an online way enjoys the same legal effect as paper contract. The fairness is the key issue in jointly signing electronic contracts by the involved participants, so that all participants can either get the same copy of the contract or nothing. Most existing solutions only focus on the fairness of electronic contract generation between two participants, where the digital signature can effectively guarantee the fairness of the exchange of electronic contracts and becomes the conventional technology in designing the contract signing protocol. In this paper, an efficient blockchain-based multi-party electronic contract signing (MECS) protocol is presented, which not only offers the fairness of electronic contract generation for multiple participants, but also allows each participant to aggregate validate the signed copy of others. Security analysis shows that the proposed MECS protocol enjoys unforgeability, non-repudiation and fairness of electronic contracts, and performance analysis demonstrates the high efficiency of our construction.
Ceph is an object-based parallel distributed file system that provides excellent performance, reliability, and scalability. Additionally, Ceph provides its Cephx authentication system to authenticate users, so that it can identify users and realize authentication. In this paper, we first model the basic architecture of Ceph using process algebra CSP (Communicating Sequential Processes). With the help of the model checker PAT (Process Analysis Toolkit), we feed the constructed model to PAT and then verify several related properties, including Deadlock Freedom, Data Reachability, Data Write Integrity, Data Consistency and Authentication. The verification results show that the original model cannot cater to the Authentication property. Therefore, we formalize a new model of Ceph where Cephx is adopted. In the light of the new verification results, it can be found that Cephx satisfies all these properties.
Kang Woo CHO Byeong-Gyu JEONG Sang Uk SHIN
The continuous development of the mobile computing environment has led to the emergence of fintech to enable convenient financial transactions in this environment. Previously proposed financial identity services mostly adopted centralized servers that are prone to single-point-of-failure problems and performance bottlenecks. Blockchain-based self-sovereign identity (SSI), which emerged to address this problem, is a technology that solves centralized problems and allows decentralized identification. However, the verifiable credential (VC), a unit of SSI data transactions, guarantees unlimited right to erasure for self-sovereignty. This does not suit the specificity of the financial transaction network, which requires the restriction of the right to erasure for credit evaluation. This paper proposes a model for VC generation and revocation verification for credit scoring data. The proposed model includes double zero knowledge - succinct non-interactive argument of knowledge (zk-SNARK) proof in the VC generation process between the holder and the issuer. In addition, cross-revocation verification takes place between the holder and the verifier. As a result, the proposed model builds a trust platform among the holder, issuer, and verifier while maintaining the decentralized SSI attributes and focusing on the VC life cycle. The model also improves the way in which credit evaluation data are processed as VCs by granting opt-in and the special right to erasure.
Dae-Hwi LEE Won-Bin KIM Deahee SEO Im-Yeong LEE
Lightweight cryptographic systems for services delivered by the recently developed Internet of Things (IoT) are being continuously researched. However, existing Public Key Infrastructure (PKI)-based cryptographic algorithms are difficult to apply to IoT services delivered using lightweight devices. Therefore, encryption, authentication, and signature systems based on Certificateless Public Key Cryptography (CL-PKC), which are lightweight because they do not use the certificates of existing PKI-based cryptographic algorithms, are being studied. Of the various public key cryptosystems, signcryption is efficient, and ensures integrity and confidentiality. Recently, CL-based signcryption (CL-SC) schemes have been intensively studied, and a multi-receiver signcryption (MRSC) protocol for environments with multiple receivers, i.e., not involving end-to-end communication, has been proposed. However, when using signcryption, confidentiality and integrity may be violated by public key replacement attacks. In this paper, we develop an efficient CL-based MRSC (CL-MRSC) scheme using CL-PKC for IoT environments. Existing signcryption schemes do not offer public verifiability, which is required if digital signatures are used, because only the receiver can verify the validity of the message; sender authenticity is not guaranteed by a third party. Therefore, we propose a CL-MRSC scheme in which communication participants (such as the gateways through which messages are transmitted) can efficiently and publicly verify the validity of encrypted messages.
Ryoga NOGUCHI Yoshikazu HANATANI Kazuki YONEYAMA
Home Energy Management Systems (HEMS) contain devices of multiple manufacturers. Also, a large number of groups of devices must be managed according to several clustering situations. Hence, since it is necessary to establish a common secret group key among group members, the group key management scheme of IEEE 802.21 is used. However, no security verification result by formal methods is known. In this paper, we give the first formal verification result of secrecy and authenticity of the group key management scheme of IEEE 802.21 against insider and outsider attacks using ProVerif, which is an automatic verification tool for cryptographic protocols. As a result, we clarify that a spoofing attack by an insider and a replay attack by an outsider are found for the basic scheme, but these attacks can be prevented by using the scheme with the digital signature option.
Akira ITO Rei UENO Naofumi HOMMA
This study presents a formal verification method for Galois-field (GF) arithmetic circuits with the characteristics of more than two values. The proposed method formally verifies the correctness of circuit functionality (i.e., the input-output relations given as GF-polynomials) by checking the equivalence between a specification and a gate-level netlist. We represent a netlist using simultaneous algebraic equations and solve them based on a novel polynomial reduction method that can be efficiently applied to arithmetic over extension fields $mathbb{F}_{p^m}$, where the characteristic p is larger than two. By using the reverse topological term order to derive the Gröbner basis, our method can complete the verification, even when a target circuit includes bugs. In addition, we introduce an extension of the Galois-Field binary moment diagrams to perform the polynomial reductions faster. Our experimental results show that the proposed method can efficiently verify practical $mathbb{F}_{p^m}$ arithmetic circuits, including those used in modern cryptography. Moreover, we demonstrate that the extended polynomial reduction technique can enable verification that is up to approximately five times faster than the original one.
In this paper, we propose a novel single-template strategy based on a mean template set and locally/globally weighted dynamic time warping (LG-DTW) to improve the performance of online signature verification. Specifically, in the enrollment phase, we implement a time series averaging method, Euclidean barycenter-based DTW barycenter averaging, to obtain a mean template set considering intra-user variability among reference samples. Then, we acquire a local weighting estimate considering a local stability sequence that is obtained analyzing multiple matching points of an optimal match between the mean template and reference sets. Thereafter, we derive a global weighting estimate based on the variable importance estimated by gradient boosting. Finally, in the verification phase, we apply both local and global weighting methods to acquire a discriminative LG-DTW distance between the mean template set and a query sample. Experimental results obtained on the public SVC2004 Task2 and MCYT-100 signature datasets confirm the effectiveness of the proposed method for online signature verification.
Nao IGAWA Tomoyuki YOKOGAWA Sousuke AMASAKI Masafumi KONDO Yoichiro SATO Kazutami ARIMOTO
Safety critical systems are often modeled using Time Petri Nets (TPN) for analyzing their reliability with formal verification methods. This paper proposed an efficient verification method for TPN introducing bounded model checking based on satisfiability solving. The proposed method expresses time constraints of TPN by Difference Logic (DL) and uses SMT solvers for verification. Its effectiveness was also demonstrated with an experiment.
Naoto SATO Hironobu KURUMA Yuichiroh NAKAGAWA Hideto OGAWA
As one type of machine-learning model, a “decision-tree ensemble model” (DTEM) is represented by a set of decision trees. A DTEM is mainly known to be valid for structured data; however, like other machine-learning models, it is difficult to train so that it returns the correct output value (called “prediction value”) for any input value (called “attribute value”). Accordingly, when a DTEM is used in regard to a system that requires reliability, it is important to comprehensively detect attribute values that lead to malfunctions of a system (failures) during development and take appropriate countermeasures. One conceivable solution is to install an input filter that controls the input to the DTEM and to use separate software to process attribute values that may lead to failures. To develop the input filter, it is necessary to specify the filtering condition for the attribute value that leads to the malfunction of the system. In consideration of that necessity, we propose a method for formally verifying a DTEM and, according to the result of the verification, if an attribute value leading to a failure is found, extracting the range in which such an attribute value exists. The proposed method can comprehensively extract the range in which the attribute value leading to the failure exists; therefore, by creating an input filter based on that range, it is possible to prevent the failure. To demonstrate the feasibility of the proposed method, we performed a case study using a dataset of house prices. Through the case study, we also evaluated its scalability and it is shown that the number and depth of decision trees are important factors that determines the applicability of the proposed method.