Mastering a complex skill like programming takes many hours. In order to encourage students to put in these hours, we built Code Hunt, a game that enables players to program against the computer with clues provided as unit tests. The game has become very popular and we are now running worldwide contests where students have a fixed amount of time to solve a set of puzzles. This paper describes Code Hunt and the contest experience it offers. We then show some early results that demonstrate how Code Hunt can accurately discriminate between good and bad coders. The challenges of creating and selecting puzzles for contests are covered. We end up with a short description of our course experience, and some figures that show that Code Hunt is enjoyed by women and men alike.

Because of the financial and other gains attached with the growing malware industry, there is a need to automate the process of malware analysis and provide real-time malware detection. To hide a malware, obfuscation techniques are used. One such technique is metamorphism encoding that mutates the dynamic binary code and changes the opcode with every run to avoid detection. This makes malware difficult to detect in real-time and generally requires a behavioral signature for detection. In this paper we present a new framework called MARD for Metamorphic Malware Analysis and Real-Time Detection, to protect the end points that are often the last defense, against metamorphic malware. MARD provides: (1) automation (2) platform independence (3) optimizations for real-time performance and (4) modularity. We also present a comparison of MARD with other such recent efforts. Experimental evaluation of MARD achieves a detection rate of 99.6% and a false positive rate of 4%.

Last year, one of the journal's two co-editors, Andy Wellings, announced that he wanted to step down by the end of 2014. That would complete an astounding 20 years of service as a co-editor. A search for Andy's replacement was successful, and his replacement is Dr. Rajkumar Buyya (or Raj for short). Raj is a professor of Computer Science at the University of Melbourne in Australia. Raj's term as co-editor commences on July 1, so that there is a transition period while Andy's work is progressively taken over by Raj. Andy will not be taking on responsibility for new submissions to the journal; they will go to Raj instead. Andy will continue to handle papers that were previously assigned to him and revisions of those papers until the end of the year. Raj's name should be well known to researchers and software practitioners in the fields of cloud computing and grid computing. At the University of Melbourne, Raj is the director of the Cloud Computing and Distributed Systems Laboratory. He is also serving as the founding CEO of Manjrasoft Pty Ltd., a spin-off company of the University, commercializing its innovations in Cloud Computing. He has a long list of accomplishments achieved during his career as a professor. These include several best paper awards, recognition awards from technical organizations, innovation awards, patents, major research grants, industrial collaborations, and a long list of publications in major journals and at major conferences. ‘A Scientometric Analysis of Cloud Computing Literature’ by German scientists reported that Raj is not only the world's most influential researcher but also the most productive one in the area of cloud computing. Originally from India, where he obtained Bachelor of Engineering and Master of Engineering degrees, Raj moved to Australia to study for his doctorate. He began his degree at the Queensland University of Technology in Brisbane, but completed it at Monash University, in Melbourne, when he was forced to find a new supervisor. His thesis on grid computing was accepted in 2002 under the supervision of Professor David Abramson. Software technologies for Grid and Cloud computing developed under Raj's leadership have gained rapid acceptance and are in use at several academic institutions and commercial enterprises in 40 countries around the world. On a personal note, Raj reports that he is married to Dr. Smrithi Buyya and they have two lovely daughters. He says he is a member of International Society for Krishna Consciousness and that one day he hopes to become a master of ‘spiritual science’! Software: Practice and Experience is fortunate that Raj has agreed to take on the role as co-editor. He has been helpful to the journal in the past, helping it achieve a more prominent position in rankings maintained by the Australian Research Council, by refereeing papers, by submitting papers, and by being a guest editor of a special issue on cloud computing. As the co-editor who will work alongside Raj, I extend a very special welcome to Raj. I am anticipating that there will be many new initiatives and a new focus for the journal, which will help it maintain its place as a leading journal, relevant to software practitioners and researchers around the world.

Dynamic binary obfuscation or metamorphism is a technique where a malware never keeps the same sequence of opcodes in the memory. Such malware are very difficult to analyse and detect manually even with the help of tools. We need to automate the analysis and detection process of such malware. This paper introduces and presents a new language named MAIL (Malware Analysis Intermediate Language) to automate and optimize this process. MAIL also provides portability for building malware analysis and detection tools. Each MAIL statement is assigned a pattern that can be used to annotate a control flow graph for pattern matching to analyse and detect metamorphic malware. Experimental evaluation of the proposed approach using an existing dataset yields malware detection rate of 93.92% and false positive rate of 3.02%.

The journal Software: Practice and Experience has now been published for 40 years. Not many authors of papers that appeared in the early days of the journal are still active in publishing research articles today. However, Dr. Barbara G. Ryder is an outstanding exception. In the October–December issue of 1974, Barbara published a groundbreaking paper with the title ‘The PFORT Verifier’ while she was working at AT&T Bell Laboratories in New Jersey. The paper described a software tool that analyzes a Fortran program and verifies that it conforms to a portable subset of the language. Although the programming language has changed and the goals have become much more ambitious, Dr. Ryder and her research group at Virginia Tech still actively work in the field of program analysis. She is also a member of the Editorial Board of this journal. In her role as one of the journal's earliest authors, I invited Dr. Ryder to write a retrospective article describing how her original work on the PFORT verifier and its software context of the 1970s are related to programming languages and software of today. The result is the paper that appears in this issue of the journal. It is co-authored by Dr. Ben Wiedermann who, until recently, was working with Barbara's research group as a visiting postdoctoral student. He is currently a visiting assistant professor at Harvey Mudd College. In their paper, Drs. Ryder and Wiedermann follow a historical thread that describes the different kinds of analyses performed on software and the reasons for performing the analyses. A recurring theme through the paper is that modern programming languages have introduced new constructs that make analysis much more challenging and that may reduce the precision of the results. The authors ask programming language designers considering new features to think carefully about their potential effects on analyzability of programs including those features.

Users of parallel patterns need to carefully consider many subtle aspects of software design. In particular, implicit relationships with hardware realities coupled with aggressive strategies for optimization are daunting in this domain. This paper proposes a new way to leverage visual cues in HiLPR, a proposed uniform representation for parallel patterns. We show the application of this approach to three design patterns: Sparse Linear Algebra, Pipeline, and Shared Queue. An evaluation of the combination of a pattern's Forces with its Solution within this representation indicates that this approach holds promise in terms of assisting developers in making better-informed decisions about pattern implementation.

Internationally each year, thousands of PhDs are awarded in Computer Science and related disciplines. While many result in conference and journal publications, one of the main thesis components, the literature review, is often not published. In recognition of the potential value of these underutilized resources,Software Practice and Experience has dedicated this Focus Section to the publication of papers based on the literature reviews that appeared in PhD theses awarded during 2008. All the submissions were subject to the Journal's normal review process and the best three papers appear here. Most software projects nowadays involve multiple developers often at multiple geographically distributed sites. Successful project development requires that these developers have a common awareness of the state of the project tasks, artefacts, and the activities of the project developers. The first paper of this Focus Section is taken from the PhD of Inrah Omoronyia entitled ‘Sharing Awareness during Distributed Collaborative Software Development’. It presents a comparison of awareness needs, and reviews how they are supported in current tools and techniques. The advent of multicore/manycore architectures, grid computing, and cloud computing has spurred much renewed interest in parallel programming activities. The second paper is taken from the PhD of Horacio Gonzalez-Velez entitled ‘Adaptive Structured Parallelism’. It presents a survey of the skeletal frameworks, which are commonly used patterns of parallel computations, communication, and coordination. These frameworks provide the control flow, nesting, resource monitoring, and portability for parallel programs. In recent years, there has been an explosion of information that is stored in databases of one form or another. Statistical Databases are databases that are used for statistical analysis purposes. They can contain potentially sensitive data and, therefore, raise significant security concerns for protecting the privacy of individuals. The final paper of this Focus Section is taken from the PhD work of Ebaa Fayyoumi entitled ‘Novel Micro-Aggregation Techniques for Secure Statistical Databases’. It surveys the fields of Statistical Disclosure Control and Micro-Aggregation techniques, which are both areas fundamentally important for ensuring that individual responses cannot be extracted from any captured data.

The Editors and Publishers of Software—Practice and Experience regret to note the passing of Per Brinch Hansen on 31 July 2007. Professor Brinch Hansen was a member of the journal's editorial board from 1979 until earlier this year. Per Brinch Hansen was a leading figure in the development of operating systems and multiprocessing concepts. His many accomplishments during a very productive lifetime included the RC 4000 multiprogramming system, the monitor concept, the Concurrent Pascal language, the Solo operating system, and the Edison programming language. Several of his most influential papers were published in this journal. His career took him from the Regnecentralen, Copenhagen, to Carnegie Mellon University, California Institute of Technology, University of California, and the University of Copenhagen. His final position, which he held up to the time of his death, was at Syracuse University in New York state. Along the way, he authored nine academic books published in the conventional manner, plus his autobiography published on the internet at http://brinch-hansen.net.

Abstract To achieve maximum efficiency, modern embedded processors for media applications exploit single instruction multiple data (SIMD) instructions. SIMD instructions provide a form of vectorization where a large machine word is viewed as a vector of subwords and the same operation is performed on all subwords in parallel. Systematic usage of SIMD instructions can significantly improve program performance. With C becoming the dominant language for programming embedded devices, there is a clear need for C compilers that use SIMD instructions whenever appropriate. However, SIMD instructions typically require each memory access to be aligned with the instruction's data access size. Therefore an important problem in designing the compiler is to determine whether a C pointer is aligned, i.e. whether it refers to the beginning of a machine word. In this paper, we describe our SIMD generation algorithm and present an analysis method which determines the alignment of pointers at compile time. The alignment information is used to reduce the number of dynamic alignment checks and the overhead incurred by them. Our method uses an interprocedural analysis which propagates pointer alignment information in function bodies and through function calls. The effectiveness of our method is supported by experimental results which show that in typical programs the alignments of about 50% of the pointers can be statically determined. Copyright © 2006 John Wiley & Sons, Ltd.

The design of software that is easy to port or deliberately targeted for multiple platforms is a neglected area of software engineering. A promising solution is to link components and toolkits through XML and reflection.

Abstract Java programmers cannot help but be aware of the advent of C#, the .NET network environment, and a host of new supporting technologies, such as Web services. Before taking the big step of moving all development to a new environment, programmers will want to know what are the advantages of C# as a language over Java, and whether the new and interesting features of C# and .NET can be incorporated into existing Java software. This paper surveys the advantages of C# and then presents and evaluates experience with connecting it to Java in a variety of ways. The first way provides evidence that Java can be linked to C# at the native code level, albeit through C++ wrappers. The second is a means for retaining the useful applet feature of Java in the server‐side architecture of Web services written in C#. The third is by providing a common XML‐based class for the development of graphical user interfaces (GUIs), which can be incorporated into Java or C#. An added advantage of this system, called Views, is that it can run independently of the resource‐intensive development environment that would otherwise be needed for using C#. A major advantage of the methods described in this paper is that in all cases the Java program is not affected by the fact that it is interfacing with C#. The paper concludes that there are many common shared technologies that bring Java and C# close together, and that innovative ways of using others can open up opportunities not hitherto imagined. Copyright © 2005 John Wiley & Sons, Ltd.

Speculative partial redundancy elimination (SPRE) uses execution profiles to improve the expected performance of programs. We show how the problem of placing expressions to achieve the optimal expected performance can be mapped to a particular kind of network flow problem and hence solved by well known techniques. Our solution is sufficiently efficient to be used in practice. Furthermore, the objective function may be chosen so that reduction in space requirements is the primary goal and execution time is secondary. One surprising result that an explosion in size may occur if speed is the sole goal, and consideration of space usage is therefore important.

This paper proposes that GUI development is as important as other aspects of programming, such as a sound understanding of control structures and object orientation. Far less attention has been paid to the programming structures for GUIs and certainly there are few cross language principles to aid the programmer. We propose that principles of GUIs can be extracted and learnt, and that they do enhance good programming practice. These principles have been implemented in our Views system which features an XML-based GUI description notation coupled with an engine that shields the programmer from much of the intricate complexity associated with events, listeners and handlers. The system is programmed primarily in C# for .NET, but is available in various forms for Java and for other platforms which support .NET through the SSCLI.

Earley's parsing algorithm is a general algorithm, able to handle any context-free grammar. As with most parsing algorithms, however, the presence of grammar rules having empty right-hand sides complicates matters. By analyzing why Earley's algorithm struggles with these grammar rules, we have devised a simple solution to the problem. Our empty-rule solution leads to a new type of finite automaton expressly suited for use in Earley parsers and to a new statement of Earley's algorithm. We show that this new form of Earley parser is much more time efficient in practice than the original.

Abstract A common problem when writing compilers for programming languages or little, domain‐specific languages is that an input token may have several interpretations, depending on context. Solutions to this problem demand programmer intervention, obfuscate the language's grammar, and may introduce subtle bugs. We present a technique which is simple and without the above drawbacks—allowing a token to simultaneously have different types—and show how it can be applied to areas such as little language processing and fuzzy parsing. We also describe ways that compiler tools can support this technique. Copyright © 2001 John Wiley & Sons, Ltd.

Abstract A novel compiler optimization for loops is presented. The optimization uses exceptions to eliminate redundant tests that are performed when code is interpretively executed, as is the case with Java bytecode executed on the Java Virtual Machine. An analysis technique based on abstract interpretation is used to discover when the optimization is applicable. Copyright © 2001 John Wiley & Sons, Ltd.

Tomita devised a method of generalized LR (GLR) parsing to parse ambiguous grammars efficiently. A GLR parser uses linear-time LR parsing techniques as long as possible, falling back on more expensive general techniques when necessary.Much research has addressed speeding up LR parsers. However, we argue that this previous work is not transferable to GLR parsers. Instead, we speed up LR parsers by building larger pushdown automata, trading space for time. A variant of the GLR algorithm then incorporates our faster LR parsers.Our timings show that our new method for GLR parsing can parse highly ambiguous grammars significantly faster than a standard GLR parser.

Java class files can be transmitted more efficiently over a network if they are compressed. After an examination of the class file structure and obtaining statistics from a large collection of class files, we propose a compression scheme that is tailored to class files. Our scheme achieves significantly better compression than commonly used methods such as ZIP. © 1998 John Wiley & Sons, Ltd.

A type inclusion test determines whether one type is a subtype of another. Efficient type testing techniques exist for single subtyping, but not for languages with multiple subtyping. To date, the fast constant-time technique relies on a binary matrix encoding of the subtype relation with quadratic space requirements. In this paper, we present three new encodings of the subtype relation, the packed encoding, the bit-packed encoding and the compact encoding. These encodings have different characteristics. The bit-packed encoding delivers the best compression rates: on average 85% for real life programs. The packed encoding performs type inclusion tests in only 4 machine instructions. We present a fast algorithm for computing these encoding which runs in less than 13 milliseconds for PE and BPE, and 23 milliseconds for CE on an Alpha processor. Finally, we compare our results with other constant-time type inclusion tests on a suite of 11 large -benchmark hierarchies.

C compilers in production environments often have to reprocess the same header files. CCC is a caching C compiler which maintains a database of partially processed header files so that repetitive work may be eliminated. © 1997 by John Wiley & Sons, Ltd.

Most practical compression methods in the LZ77 and LZ78 families parse their input using a greedy heuristic. However the popular gzip compression program demonstrates that modest but significant gains in compression performance are possible if non-greedy parsing is used. Practical implementations for using non-greedy parsing in LZ77 and LZ78 compression are explored and some experimental measurements are presented.

Two highly effective families of lossless compression methods were created by Ziv and Lempel (1977). However, these methods are normally ineffective when applied to digitized signals. We have successfully adapted the LZ77 method to take advantage of the repetitive nature of ECG waveforms. In our experiments, the resulting algorithm produces much better compression ratios than competing techniques while retaining the essential characteristics of the waveform.>

Text compression algorithms are normally defined in terms of a source alphabet Sigma of 8-bit ASCII codes. The authors consider choosing Sigma to be an alphabet whose symbols are the words of English or, in general, alternate maximal strings of alphanumeric characters and nonalphanumeric characters. The compression algorithm would be able to take advantage of longer-range correlations between words and thus achieve better compression. The large size of Sigma leads to some implementation problems, but these are overcome to construct word-based LZW, word-based adaptive Huffman, and word-based context modelling compression algorithms.>

The Lempel-Ziv-Welch compression algorithm is widely used because it achieves an excellent compromise between compression performance and speed of execution. A simple way to improve the compression without significantly degrading its speed is proposed, and experimental data show that it works in practice. Even better results are achieved with additional optimization of 'phasing in' binary numbers.>

A method of dynamically constructing Markov chain models that describe the characteristics of binary messages is developed. Such models can be used to predict future message characters and can therefore be used as a basis for data compression. To this end, the Markov modelling technique is combined with Guazzo's arithmetic coding scheme to produce a powerful method of data compression. The method has the advantage of being adaptive: messages may be encoded or decoded with just a single pass through the data. Experimental results reported here indicate that the Markov modelling approach generally achieves much better data compression than that observed with competing methods on typical computer data.

Abstract Authors of papers on LR parser table compaction and authors of books on compiler construction appear to have either overlooked or discounted the possibility of using hashing. In fact, hashing is easy to implement as a compaction technique and gives reasonable performance. It produces tables that are as compact as some of the other techniques reported in the literature while permitting efficient table lookups.

Abstract Mkscan is a tool for generating and editing scanners. It has been designed with ease of use in mind. The tol is interactive and uses a full screen interface. No attempt is made to provide an all‐purpose tool that can generate a recognizer for any regular language. Instead, mkscan has been tailored to suit the lexical structure of common programming languages and command languages. Using mkscan, a scanner for Pascal can be created in under ten minutes–including the time taken to type the list of keywords.

A practical method is presented that permits retrieval from a table in constant time. The method is suitable for large tables and consumes, in practice, O(n) space for n table elements. In addition, the table and the hashing function can be constructed in O(n) expected time. Variations of the method that offer different compromises between storage usage and update time are presented.

Abstract A new methodology for code generation in compilers is advanced. The underlying principle is a simple one—that machine memory resources must be matched to intermediate code values. It is possible to view the methodology as a generalization of the Graham‐Glanville approach, but where there is a wider‐ranging search for the best code sequences. This new approach has been implemented for the IBM/370, the VAX‐11 and the Intel 8086 instruction sets.

The problem of minimizing the lengths of bit vectors used to implement sets in Pascal is considered. An analysis algorithm is presented that determines these minimum lengths. It is proved that two passes are both necessary and sufficient. Implementation concerns involving sets and the analysis algorithm itself are considered.

In the above paper,1Baber describes a scheme for representing data items with unlimited length. We would like to argue that this scheme is not very different from other published schemes and that his scheme is not obviously useful for the proposed application.

A crucial problem in the decompilation or disassembly of computer programs is the identification of executable code, i.e. the separation of instructions from data. This problem, for most computer architectures, is equivalent to the Halting Problem and is therefore unsolvable in general. The problem of identifying instructions is examined in this paper and an algorithm that will ‘usually’ perform a correct analysis is described. In addition, other aspects of disassembly are discussed and algorithms outlined.

Previous article Full AccessCorrigendum. A New Representation of the Rational Numbers for Fast Easy ArithmeticE. C. R. Hehner and R. N. S. HorspoolE. C. R. Hehner and R. N. S. Horspoolhttps://doi.org/10.1137/0209019PDFBibTexSections ToolsAdd to favoritesExport CitationTrack CitationsEmail SectionsAbout"Corrigendum. A New Representation of the Rational Numbers for Fast Easy Arithmetic." SIAM Journal on Computing, 9(1), p. 217 Previous article FiguresRelatedReferencesCited ByDetails Volume 9, Issue 1| 1980SIAM Journal on Computing History Submitted:12 July 1979Published online:13 July 2006 InformationCopyright © 1980 Society for Industrial and Applied MathematicsPDF Download Article & Publication DataArticle DOI:10.1137/0209019Article page range:pp. 217-217ISSN (print):0097-5397ISSN (online):1095-7111Publisher:Society for Industrial and Applied Mathematics

Abstract The problem of searching through text to find a specified substring is considered in a practical setting. It is discovered that a method developed by Boyer and Moore can outperform even special‐purpose search instructions that may be built into the computer hardware. For very short substrings however, these special purpose instructions are fastest—provided that they are used in an optimal way.

A novel system for representing the rational numbers based on Hensel’s p-adic arithmetic is proposed. The new scheme uses a compact variable-length encoding that may be viewed as a generalization of radix complement notation. It allows exact arithmetic, and approximate arithmetic under programmer control. It is superior to existing coding methods because the arithmetic operations take particularly simple, consistent forms. These attributes make the new number representation attractive for use in computer hardware.

The p-adic number system is introduced and developed into a form suitable for performing exact arithmetic in computers. The proposed representation has several desirable attributes: the four standard arithmetic operations have a simple consistent form, the programmer has the ability to choose the precise degree of accuracy in his calculations and the variable-length nature of the representation achieves compact encodings.