Control-flow integrity (CFI) is a general term for computer security techniques that prevent a wide variety of malware attacks from redirecting the flow of execution (the control flow) of a program. == Background == A computer program commonly changes its control flow to make decisions and use different parts of the code. Such transfers may be direct, in that the target address is written in the code itself, or indirect, in that the target address itself is a variable in memory or a CPU register. In a typical function call, the program performs a direct call, but returns to the caller function using the stack – an indirect backward-edge transfer. When a function pointer is called, such as from a virtual table, we say there is an indirect forward-edge transfer. Attackers seek to inject code into a program to make use of its privileges or to extract data from its memory space. Before executable code was commonly made read-only, an attacker could arbitrarily change the code as it is run, targeting direct transfers or even do with no transfers at all. After W^X became widespread, an attacker wants to instead redirect execution to a separate, unprotected area containing the code to be run, making use of indirect transfers: one could overwrite the virtual table for a forward-edge attack or change the call stack for a backward-edge attack (return-oriented programming). CFI is designed to protect indirect transfers from going to unintended locations. == Techniques == Associated techniques include code-pointer separation (CPS), code-pointer integrity (CPI), stack canaries, shadow stacks (SS), and vtable pointer verification. These protections can be classified into either coarse-grained or fine-grained based on the number of targets restricted. A coarse-grained forward-edge CFI implementation, could, for example, restrict the set of indirect call targets to any function that may be indirectly called in the program, while a fine-grained one would restrict each indirect call site to functions that have the same type as the function to be called. Similarly, for a backward edge scheme protecting returns, a coarse-grained implementation would only allow the procedure to return to a function of the same type (of which there could be many, especially for common prototypes), while a fine-grained one would enforce precise return matching (so it can return only to the function that called it). == Implementations == Related implementations are available in Clang (LLVM front-end),, GNU Compiler Collection, Microsoft's Control Flow Guard and Return Flow Guard, Google's Indirect Function-Call Checks and Reuse Attack Protector (RAP). === LLVM/Clang === The LLVM compiler's C/C++ front-end Clang provides a number of "CFI" schemes that works on the forward edge by checking for errors in virtual tables and type casts. Not all of the schemes are supported on all platforms and most of them, the exception being two "kcfi" schemes intended for low-level kernel software, depends on link-time optimization (LTO) to know what functions are supposed to be called in normal cases. Also provided is a separate "shadow call stack" (SCS) instrumentation pass that defends on the backward edge by checking for call stack modifications, available only for the aarch64 and RISC-V ISAs. And due to use of a shared processor register SCS is only enforceable on certain ABIs or if in other ways it is ensured that any other software using the register set (thread/processor) does not interfere with this use. Google has shipped Android with the Linux kernel compiled by Clang with link-time optimization (LTO) and CFI enabled since 2018. Even though SCS is available for the Linux kernel as an option, and support is also available for Android's system components it is recommended only to enable it for components for which it can be ensured that no third party code is loaded. === GCC === The GNU Compiler Collection implemented a "shadow call stack" compatible with Clang for aarch64 in v12 released in 2022. This feature is primarily intended for building the Linux kernel as support is missing from GCC user space libraries. === Intel Control-flow Enforcement Technology === Intel Control-flow Enforcement Technology (CET) detects compromises to control flow integrity with a shadow stack (SS) and indirect branch tracking (IBT). The kernel must map a region of memory for the shadow stack not writable to user space programs except by special instructions. The shadow stack stores a copy of the return address of each CALL. On a RET, the processor checks if the return address stored in the normal stack and shadow stack are equal. If the addresses are not equal, the processor generates an INT #21 (Control Flow Protection Fault). Indirect branch tracking detects indirect JMP or CALL instructions to unauthorized targets. It is implemented by adding a new internal state machine in the processor. The behavior of indirect JMP and CALL instructions is changed so that they switch the state machine from IDLE to WAIT_FOR_ENDBRANCH. In the WAIT_FOR_ENDBRANCH state, the next instruction to be executed is required to be the new ENDBRANCH instruction (ENDBR32 in 32-bit mode or ENDBR64 in 64-bit mode), which changes the internal state machine from WAIT_FOR_ENDBRANCH back to IDLE. Thus every authorized target of an indirect JMP or CALL must begin with ENDBRANCH. If the processor is in a WAIT_FOR_ENDBRANCH state (meaning, the previous instruction was an indirect JMP or CALL), and the next instruction is not an ENDBRANCH instruction, the processor generates an INT #21 (Control Flow Protection Fault). On processors not supporting CET indirect branch tracking, ENDBRANCH instructions are interpreted as NOPs and have no effect. === Microsoft Control Flow Guard === Control Flow Guard (CFG) was first released for Windows 8.1 Update 3 (KB3000850) in November 2014. Developers can add CFG to their programs by adding the /guard:cf linker flag before program linking in Visual Studio 2015 or newer. As of Windows 10 Creators Update (Windows 10 version 1703), the Windows kernel is compiled with CFG. The Windows kernel uses Hyper-V to prevent malicious kernel code from overwriting the CFG bitmap. CFG operates by creating a per-process bitmap, where a set bit indicates that the address is a valid destination. Before performing each indirect function call, the application checks if the destination address is in the bitmap. If the destination address is not in the bitmap, the program terminates. This makes it more difficult for an attacker to exploit a use-after-free by replacing an object's contents and then using an indirect function call to execute a payload. ==== Implementation details ==== For all protected indirect function calls, the _guard_check_icall function is called, which performs the following steps: Convert the target address to an offset and bit number in the bitmap. The highest 3 bytes are the byte offset in the bitmap The bit offset is a 5-bit value. The first four bits are the 4th through 8th low-order bits of the address. The 5th bit of the bit offset is set to 0 if the destination address is aligned with 0x10 (last four bits are 0), and 1 if it is not. Examine the target's address value in the bitmap If the target address is in the bitmap, return without an error. If the target address is not in the bitmap, terminate the program. ==== Bypass techniques ==== There are several generic techniques for bypassing CFG: Set the destination to code located in a non-CFG module loaded in the same process. Find an indirect call that was not protected by CFG (either CALL or JMP). Use a function call with a different number of arguments than the call is designed for, causing a stack misalignment, and code execution after the function returns (patched in Windows 10). Use a function call with the same number of arguments, but one of pointers passed is treated as an object and writes to a pointer-based offset, allowing overwriting a return address. Overwrite the function call used by the CFG to validate the address (patched in March 2015) Set the CFG bitmap to all 1's, allowing all indirect function calls Use a controlled-write primitive to overwrite an address on the stack (since the stack is not protected by CFG) === Microsoft eXtended Flow Guard === eXtended Flow Guard (XFG) has not been officially released yet, but is available in the Windows Insider preview and was publicly presented at Bluehat Shanghai in 2019. XFG extends CFG by validating function call signatures to ensure that indirect function calls are only to the subset of functions with the same signature. Function call signature validation is implemented by adding instructions to store the target function's hash in register r10 immediately prior to the indirect call and storing the calculated function hash in the memory immediately preceding the target address's code. When the indirect call is made, the XFG validation function compares the value in r10 to the target
IRows
iRows was a web-based spreadsheet in beta with a GUI similar to the traditional desktop-based spreadsheet applications, such as Microsoft Excel and OpenOffice.org. It was shut down on December 31, 2006, after it was announced that its two founders had been hired by Google. iRows used Ajax and XML. It was described as an example of a Web 2.0 system. iRows supported conventional spreadsheet features functions, value formatting and charts and added web oriented spreadsheet capabilities like collaboration (multiple people using a shared spreadsheet, sending a spreadsheet as a link instead of an attachment and ability to publish spreadsheets on other web pages (e.g. blogs).
METEO System
The METEO System is a machine translation system specifically designed for the translation of the weather forecasts issued daily by Environment Canada. The system was used from 1981 to 30 September 2001 by Environment Canada to translate forecasts issued in French in the province of Quebec into English and those issued in English in other Canadian provinces into French. Since then, a competitor program has replaced METEO System after an open governmental bid. The system was developed by John Chandioux and was often mentioned as one of the few success stories in the field of machine translation. == History == The METEO System was in operational use at Environment Canada from 1982 to 2001. It stems from a prototype developed in 1975–76 by the TAUM Group, known as TAUM-METEO. The initial motivation to develop that prototype was that a junior translator came to TAUM to ask for help in translating weather bulletins at Environment Canada. Since all official communications emanating from the Canadian government must be available in French and English, because of the Official Languages Act of 1969, and weather bulletins represent a large amount of translation in real time, junior translators had to spend several months producing first draft translations, which were then revised by seniors. That was a difficult and tedious job, because of the specificities of the English and French sublanguages used, and not very rewarding, as the lifetime of a bulletin is only 4 hours. TAUM proposed to build a prototype MT system, and Environment Canada agreed to fund the project. A prototype was ready after a few months, with basic integration in the workflow of translation (source and target bulletins travelled over telex lines at the time and MT happened on a mainframe computer). The first version of the system (METEO 1) went into operation on a Control Data CDC 7600 supercomputer in March 1977. Chandioux then left the TAUM group to manage its operation and improve it, while the TAUM group embarked on a different project (TAUM-aviation, 1977–81). Benoit Thouin made improvements to the initial prototype over the subsequent year, and turned it into an operational system. After three years, METEO 1 had demonstrated the feasibility of microcomputer-based machine translation to the satisfaction of the Canadian government's Translation Bureau of Public Works and Government Services Canada. METEO 1 was formally adopted in 1981, replacing the junior translators in the workflow. Because of the need for high-quality translation, the revision step, done by senior translators, was maintained. The quality, measured as the percentage of edit operations (inserting or deleting a word counts as 1, replacing as 2) on the MT results, reached 85% in 1985. Until that time, the MT part was still implemented as a sequence of Q-systems. The Q-systems formalism is a rule-based SLLP (Specialized Language for Linguistic Programming) invented by Alain Colmerauer in 1967 as he was a postdoc coopérant at the TAUM group. He later invented the Prolog language in 1972 after returning to France and becoming a university professor in Marseille-Luminy. As the engine of the Q-systems is highly non-deterministic, and the manipulated data structures are in some ways too simple, without any types such as string or number, Chandioux encountered limitations in his efforts to raise translation quality and lower computation time to the point he could run it on microcomputers. In 1981, Chandioux created a new SLLP, or metalanguage for linguistic applications, based on the same basic algorithmic ideas as the Q-systems, but more deterministic, and offering typed labels on tree nodes. Following the advice of Bernard Vauquois and Colmerauer, he created GramR, and developed it for microcomputers. In 1982, he could start developing in GramR a new system for translating the weather bulletins on a high-end Cromemco microcomputer. METEO 2 went into operation in 1983. The software then ran in 48Kb of central memory with a 5Mb hard disk for paging. METEO 2 was the first MT application to run on a microcomputer. In 1985, the system had nothing left of the initial prototype, and was officially renamed METEO. It translated about 20 million words per year from English into French, and 10 million words from French into English, with a quality of 97%. Typically, it took 4 minutes for a bulletin in English to be sent from Winnipeg and come back in French after MT and human revision. In 1996, Chandioux developed a special version of his system (METEO 96) which was used to translate the weather forecasts (different kinds of bulletins) issued by the US National Weather Service during the 1996 Summer Olympics in Atlanta. The last known version of the system, METEO 5, dates from 1997 and ran on an IBM PC network under Windows NT. It translated 10 pages per second, but was able to fit into a 1.44Mb floppy disk.
Steve Omohundro
Stephen Malvern Omohundro (born 1959) is an American computer scientist whose areas of research include Hamiltonian physics, dynamical systems, programming languages, machine learning, machine vision, and the social implications of artificial intelligence. His current work uses rational economics to develop safe and beneficial intelligent technologies for better collaborative modeling, understanding, innovation, and decision making. == Education == Omohundro has degrees in physics and mathematics from Stanford University (Phi Beta Kappa) and a Ph.D. in physics from the University of California, Berkeley. == Learning algorithms == Omohundro started the "Vision and Learning Group" at the University of Illinois, which produced 4 Masters and 2 Ph.D. theses. His work in learning algorithms included a number of efficient geometric algorithms, the manifold learning task and various algorithms for accomplishing this task, other related visual learning and modelling tasks, the best-first model merging approach to machine learning (including the learning of Hidden Markov Models and Stochastic Context-free Grammars), and the Family Discovery Learning Algorithm, which discovers the dimension and structure of a parameterized family of stochastic models. == Self-improving artificial intelligence and AI safety == Omohundro started Self-Aware Systems in Palo Alto, California to research the technology and social implications of self-improving artificial intelligence. He is an advisor to the Machine Intelligence Research Institute on artificial intelligence. He argues that rational systems exhibit problematic natural "drives" that will need to be countered in order to build intelligent systems safely. His papers, talks, and videos on AI safety have generated extensive interest. He has given many talks on self-improving artificial intelligence, cooperative technology, AI safety, and connections with biological intelligence. == Programming languages == At Thinking Machines Corporation, Cliff Lasser and Steve Omohundro developed Star Lisp, the first programming language for the Connection Machine. Omohundro joined the International Computer Science Institute (ICSI) in Berkeley, California, where he led the development of the open source programming language Sather. Sather is featured in O'Reilly's History of Programming Languages poster. == Physics and dynamical systems theory == Omohundro's book Geometric Perturbation Theory in Physics describes natural Hamiltonian symplectic structures for a wide range of physical models that arise from perturbation theory analyses. He showed that there exist smooth partial differential equations which stably perform universal computation by simulating arbitrary cellular automata. The asymptotic behavior of these PDEs is therefore logically undecidable. With John David Crawford he showed that the orbits of three-dimensional period doubling systems can form an infinite number of topologically distinct torus knots and described the structure of their stable and unstable manifolds. == Mathematica and Apple tablet contest == From 1986 to 1988, he was an Assistant Professor of Computer science at the University of Illinois at Urbana-Champaign and cofounded the Center for Complex Systems Research with Stephen Wolfram and Norman Packard. While at the University of Illinois, he worked with Stephen Wolfram and five others to create the symbolic mathematics program Mathematica. He and Wolfram led a team of students that won an Apple Computer contest to design "The Computer of the Year 2000." Their design entry "Tablet" was a touchscreen tablet with GPS and other features that finally appeared when the Apple iPad was introduced 22 years later. == Other contributions == Subutai Ahmad and Steve Omohundro developed biologically realistic neural models of selective attention. As a research scientist at the NEC Research Institute, Omohundro worked on machine learning and computer vision, and was a co-inventor of U.S. Patent 5,696,964, "Multimedia Database Retrieval System Which Maintains a Posterior Probability Distribution that Each Item in the Database is a Target of a Search." === Pirate puzzle === Omohundro developed an extension to the game theoretic pirate puzzle featured in Scientific American. == Outreach == Omohundro has sat on the Machine Intelligence Research Institute board of advisors. He has written extensively on artificial intelligence, and has warned that "an autonomous weapons arms race is already taking place" because "military and economic pressures are driving the rapid development of autonomous systems".
Dynamic topic model
Within statistics, Dynamic topic models' are generative models that can be used to analyze the evolution of (unobserved) topics of a collection of documents over time. This family of models was proposed by David Blei and John Lafferty and is an extension to Latent Dirichlet Allocation (LDA) that can handle sequential documents. In LDA, both the order the words appear in a document and the order the documents appear in the corpus are oblivious to the model. Whereas words are still assumed to be exchangeable, in a dynamic topic model the order of the documents plays a fundamental role. More precisely, the documents are grouped by time slice (e.g.: years) and it is assumed that the documents of each group come from a set of topics that evolved from the set of the previous slice. == Topics == Similarly to LDA and pLSA, in a dynamic topic model, each document is viewed as a mixture of unobserved topics. Furthermore, each topic defines a multinomial distribution over a set of terms. Thus, for each word of each document, a topic is drawn from the mixture and a term is subsequently drawn from the multinomial distribution corresponding to that topic. The topics, however, evolve over time. For instance, the two most likely terms of a topic at time t could be "network" and "Zipf" (in descending order) while the most likely ones at time t+1 could be "Zipf" and "percolation" (in descending order). == Model == Define α t {\displaystyle \alpha _{t}} as the per-document topic distribution at time t. β t , k {\displaystyle \beta _{t,k}} as the word distribution of topic k at time t. η t , d {\displaystyle \eta _{t,d}} as the topic distribution for document d in time t, z t , d , n {\displaystyle z_{t,d,n}} as the topic for the nth word in document d in time t, and w t , d , n {\displaystyle w_{t,d,n}} as the specific word. In this model, the multinomial distributions α t + 1 {\displaystyle \alpha _{t+1}} and β t + 1 , k {\displaystyle \beta _{t+1,k}} are generated from α t {\displaystyle \alpha _{t}} and β t , k {\displaystyle \beta _{t,k}} , respectively. Even though multinomial distributions are usually written in terms of the mean parameters, representing them in terms of the natural parameters is better in the context of dynamic topic models. The former representation has some disadvantages due to the fact that the parameters are constrained to be non-negative and sum to one. When defining the evolution of these distributions, one would need to assure that such constraints were satisfied. Since both distributions are in the exponential family, one solution to this problem is to represent them in terms of the natural parameters, that can assume any real value and can be individually changed. Using the natural parameterization, the dynamics of the topic model are given by β t , k | β t − 1 , k ∼ N ( β t − 1 , k , σ 2 I ) {\displaystyle \beta _{t,k}|\beta _{t-1,k}\sim N(\beta _{t-1,k},\sigma ^{2}I)} and α t | α t − 1 ∼ N ( α t − 1 , δ 2 I ) {\displaystyle \alpha _{t}|\alpha _{t-1}\sim N(\alpha _{t-1},\delta ^{2}I)} . The generative process at time slice 't' is therefore: Draw topics β t , k | β t − 1 , k ∼ N ( β t − 1 , k , σ 2 I ) ∀ k {\displaystyle \beta _{t,k}|\beta _{t-1,k}\sim N(\beta _{t-1,k},\sigma ^{2}I)\forall k} Draw mixture model α t | α t − 1 ∼ N ( α t − 1 , δ 2 I ) {\displaystyle \alpha _{t}|\alpha _{t-1}\sim N(\alpha _{t-1},\delta ^{2}I)} For each document: Draw η t , d ∼ N ( α t , a 2 I ) {\displaystyle \eta _{t,d}\sim N(\alpha _{t},a^{2}I)} For each word: Draw topic Z t , d , n ∼ Mult ( π ( η t , d ) ) {\displaystyle Z_{t,d,n}\sim {\textrm {Mult}}(\pi (\eta _{t,d}))} Draw word W t , d , n ∼ Mult ( π ( β t , Z t , d , n ) ) {\displaystyle W_{t,d,n}\sim {\textrm {Mult}}(\pi (\beta _{t,Z_{t,d,n}}))} where π ( x ) {\displaystyle \pi (x)} is a mapping from the natural parameterization x to the mean parameterization, namely π ( x i ) = exp ( x i ) ∑ i exp ( x i ) {\displaystyle \pi (x_{i})={\frac {\exp(x_{i})}{\sum _{i}\exp(x_{i})}}} . == Inference == In the dynamic topic model, only W t , d , n {\displaystyle W_{t,d,n}} is observable. Learning the other parameters constitutes an inference problem. Blei and Lafferty argue that applying Gibbs sampling to do inference in this model is more difficult than in static models, due to the nonconjugacy of the Gaussian and multinomial distributions. They propose the use of variational methods, in particular, the Variational Kalman Filtering and the Variational Wavelet Regression. == Applications == In the original paper, a dynamic topic model is applied to the corpus of Science articles published between 1881 and 1999 aiming to show that this method can be used to analyze the trends of word usage inside topics. The authors also show that the model trained with past documents is able to fit documents of an incoming year better than LDA. A continuous dynamic topic model was developed by Wang et al. and applied to predict the timestamp of documents. Going beyond text documents, dynamic topic models were used to study musical influence, by learning musical topics and how they evolve in recent history.
Shaded Picture System
The Shaded Picture System was a 3D raster computer display processor introduced by Evans & Sutherland in October 1973. The Shaded Picture System was the first general-purpose, commercially available raster computer graphics display processor capable of real-time, shaded 3D graphics. It could only display black and white graphics at a resolution of 256 by 256. It was extremely expensive, and very few units were ever sold. == History == The principles of shaded, hidden-line true 3D graphics were pioneered at the University of Utah in 1967. However, this algorithm was slow and would take several minutes to produce an image. In 1970, Gary Watkins developed a FORTRAN simulator of a faster algorithm that would theoretically generate shaded 3D images in real-time, "if implemented in suitable hardware". The simulator itself was still not capable of real-time shaded 3D image rendering. Evans & Sutherland developed a functional prototype of this "suitable hardware", which was later sold as the Shaded Picture System in 1973. About a year earlier in 1972, Evans & Sutherland sold the first and only CT1 to Case Western Reserve University. The CT1, or Continuous Tone 1, was a specialized image generator, not meant as a marketable or mass-produced product. At the time, the CT1, along with G.E./NASA's upgraded Electronic Scene Generator from 1971, would have been the only real-time raster graphics systems sold to customers comparable to the Shaded Picture System, although both the CT1 and Electronic Scene Generator were intentionally produced as one-off products and specialized for the needs of their customers. The Shaded Picture System, in contrast, was intentionally marketed.In early 1975, Evans & Sutherland demonstrated a random-access video frame buffer using relatively low-cost semiconductor memory, which was much more capable than the Shaded Picture System. When interfaced with a (non-shaded) E&S Picture System, the frame buffer had a resolution of 512 by 512 in grayscale and partial color capabilities. By the end of 1975, this frame buffer was commercially available.
Cheng Xiang Zhai
ChengXiang Zhai is a computer scientist. He is a Donald Biggar Willett Professor in Engineering in the Department of Computer Science at the University of Illinois at Urbana-Champaign. == Biography == Zhai received the BS (1984), MS (1987, under Guoliang Zheng), and PhD (1990, under Jiafu Xu) in Computer Science from Nanjing University. He spent 1990 to 1993 working at Nanjing University's State Key Laboratory for Novel Software Technology. In 1993, he left for America to pursue a second PhD, this time at Carnegie Mellon University (CMU) with David A. Evans. Evans then left to spend more time with the company ClariTech. Zhai obtained from CMU a MS (1997) in computational linguistics and then started working with John Lafferty. He finally received from CMU a PhD in Language and Information Technologies in 2002. Since then, he has been an Assistant Professor (2002–2008), Associate Professor (2008–2013), Professor (2013–2018), and Donald Biggar Willett Professor (2018–) at the UIUC Department of Computer Science. He also holds joint appointments with the Carl R. Woese Institute for Genomic Biology, Department of Statistics, and School of Information Sciences at UIUC. == Awards == ACM SIGIR Gerard Salton Award, 2021, "for significant and sustained contributions to information retrieval and data science. His work has defined many of the theoretical foundations of the language modeling approach, yielding major insights into areas such as smoothing methods, relevance feedback, topic diversification, and text representations that incorporate positional information. He and his collaborators have also pioneered the axiomatic approach to information retrieval, which continues to provide inspiration for retrieval model and evaluation research." ACM SIGIR Academy inductee, 2021 ACM Fellow, 2017, "for contributions to information retrieval and text data mining." ACM SIGIR Test of Time Award, 2016, for paper A study of smoothing methods for language models applied to Ad Hoc information retrieval ACM SIGIR Test of Time Award, 2016, for paper Document language models, query models, and risk minimization for information retrieval ACM SIGIR Test of Time Award, 2014, for paper Beyond independent relevance: methods and evaluation metrics for subtopic retrieval ACM Distinguished Member, 2009 Presidential Early Career Award for Scientists and Engineers (PECASE), 2004, "for his work on user-centered, adaptive intelligent information access. His techniques expect to improve search-engine performance, support better information organization and enable understanding of large volumes of information. Zhai's work in information retrieval is expected to enhance curricula and provide new educational tools for the growing information technology workforce." ACM SIGIR Best Paper Award, 2004, for paper A formal study of information retrieval heuristics == Personal == Zhai's son Alex has earned three medals at the International Mathematical Olympiad.