META-GUI: Towards Multi-modal Conversational Agents on Mobile GUI

Proceedings of the 2022 Conference on Empirical Methods in Natural Language Processing, pages 706 - 714 December 7-11, 2022 ©2022 Association for Computational Linguistics Segmenting Numerical Substitution Ciphers Nada Aldarrab Department of Information Technology King Abdulaziz University Jeddah, Saudi Arabia nialdarrab@kau.edu.sa Jonathan May† Information Sciences Institute University of Southern California Marina del Rey, California, USA jonmay@isi.edu Abstract Deciphering historical substitution ciphers is a challenging problem. Example problems that have been previously studied include detecting cipher type, detecting plaintext language, and acquiring the substitution key for segmented ciphers. However, attacking unsegmented ci- phers is still a challenging task. Segmentation (i.e. finding substitution units) is essential for cracking those ciphers. In this work, we pro- pose the first automatic methods to segment those ciphers using Byte Pair Encoding (BPE) and unigram language models. Our methods achieve an average segmentation error of 2% on 100 randomly-generated monoalphabetic ci- phers and 27% on 3 real historical homophonic ciphers. We also propose a method for solving non-deterministic ciphers with existing keys us- ing a lattice and a pretrained language model. Our method leads to the full solution of the IA cipher; a real historical cipher that has not been fully solved until this work. 1 Introduction The contents of thousands of historical documents are still unknown to the contemporary age, even though they are encrypted using classical methods. Example documents include books from secret so- cieties, diplomatic correspondences, and pharma- cological books. Previous work has been done on collecting historical ciphers from libraries and archives and making them available for researchers (Megyesi et al., 2019, 2020). However, decipher- ment of classical ciphers is an essential step to reveal the contents of those historical documents. Methods for deciphering historical substitution ciphers have been proposed by the natural language processing community (Ravi and Knight, 2008; Corlett and Penn, 2010; Nuhn et al., 2013, 2014; Hauer et al., 2014; Aldarrab, 2017; Kambhatla et al., 2018; Aldarrab and May, 2021). However, †Work done prior to JM joining Amazon. these methods all assume that cipher elements, or substitution units, are clearly segmented (i.e., that token boundaries are well established). Many his- torical documents, however, are enciphered as con- tinuous sequences of digits that hide token bound- aries (Lasry et al., 2020). An example cipher (the IA cipher) is shown in Figure 1 (Megyesi et al., 2019). Solving those ciphers is very challenging since it is not possible to directly search for the key without finding substitution units. We use the term numerical ciphers to refer to these unsegmented substitution ciphers.1 In this work, we address the problem of seg- menting numerical ciphers. The contributions of our work are: • We propose novel unsupervised methods to segment numerical ciphers with no existing keys using Byte Pair Encoding (BPE) (Gage, 1994) and unigram language models (Kudo, 2018). • We conduct extensive testing of our methods on different cipher types. We report results on synthetic and real historical ciphers and show how performance varies with cipher type and length. Our methods achieve an …

Content truncated to 500 words