bluuebunny/crossref_metadata_2025 huggingface dataset:
A multi-institutional investigation of computer science seniors' knowledge of programming concepts
Authors: Murphy Laurie , McCauley Renée , Westbrook Suzanne , Fossum Timothy , Haller Susan , Morrison Briana B. , Richards Brad , Sanders Kate , Zander Carol , Anderson Ruth E.
Published: November 2005

Research on learning suggests the importance of helping students organize their knowledge around meaningful patterns of information. This paper reports on a multi-institutional study to investigate how senior computer science majors articulate and organize their knowledge of programming concepts using a card-sorting technique adopted from knowledge acquisition. We show that card-sorts are an effective means of eliciting students' knowledge structures and suggest they can also be used to help students organize their knowledge throughout the curriculum.
Experiences teaching operating systems using virtual platforms and linux
Authors: Nieh Jason , Vaill Chris
Published: November 2005

Operating system courses teach students much more when they provide hands-on kernel-level project experience with a real operating system. However, enabling a large class of students to do kernel development can be difficult. To address this problem, we created a virtual kernel development environment in which operating systems can be developed, debugged, and rebooted in a shared computer facility without affecting other users. Using virtual machines and remote display technology, our virtual kernel development laboratory enables even distance learning students at remote locations to participate in kernel development projects with on-campus students. We have successfully deployed and used our virtual kernel development environment together with the open-source Linux kernel to provide kernel-level project experiences for over nine hundred students in the introductory operating system course at Columbia University.
Configuring a multi-course lab for system-level projects
Authors: Adams Joel C. , Laverell W. David
Published: November 2005

Having students modify an actual operating system kernel or network protocol stack opens their eyes to what is going on "beneath the hood" of a computer. However student modifications to a system may result in an unstable computer. Because of this, giving students such experience has in the past required a lab and/or computers dedicated to the students in the system-level course, and computer science departments without such dedicated facilities have been unable to provide their students with system-level experience. In this paper, we present two ways of giving students system-level experience in a non-dedicated lab; one using commercial software (VMWare), and another using open-source freeware (User Mode Linux Kernel).
We've been working on the railroad
Authors: McCormick John W.
Published: November 2005

This paper describes a laboratory used to support a junior level course in real-time embedded software development. Thirteen years of data comparing programming languages for a real-time systems course are presented. Funding provided by the Maytag Corporation and Rockwell-Collins makes it possible to provide other schools with low cost electronics necessary to duplicate this laboratory with a minimum of effort.
Fostering a creative interest in computer science
Authors: Lewandowski Gary , Johnson Elizabeth , Goldweber Michael
Published: November 2005

In this paper, we describe activities undertaken at our university to revise our computer science program to develop an environment and curriculum which encourages creative, hands-on learning by our students. Our main changes were the development of laboratory space, increased hands-on problem solving activities in the introductory course, open-ended programming projects in the early courses including a requirement of an open-ended project extension for an A grade, and the integration of a seminar into the senior project requirement. Our results suggest that these changes have improved student skill and willingness to deal with new problems and technologies. An additional surprising side-effect appears to be a dramatic increase in retention over the first two years, despite lower overall grade averages in those courses.
Intra-curriculum software engineering education
Authors: Fenwick James B. , Kurtz Barry L.
Published: November 2005

We have been funded by the National Science Foundation to investigate the feasibility of distributing large software engineering projects across the academic curriculum (DUE 0127439). This paper reports on the pedagogical aspects of the intra-curriculum methodology we have developed including motivation, goals, instructor responsibilities, and variations of the approach. The paper also reports on three applications of the methodology including lessons learned.
Game design & programming concentration within the computer science curriculum
Authors: Coleman Ron , Krembs Mary , Labouseur Alan , Weir Jim
Published: November 2005

This paper describes initiatives at Marist College to develop a Game Concentration in the undergraduate Computer Science curriculum. These initiatives contemplate recommendations for existing courses as well as adoption of new courses. We also consider activities of the Association of Computing Machinery (ACM) in this area and opportunities for students beyond the classroom.
The many facets of diversity
Authors: Beidler Jack , Holz Hilary , Yasuhara Ken , Adams Evans J.
Published: November 2005

The panelists approach diversity from different points of view and experiences to produce a positive and productive foundation for an open discussion on the many facets of diversity, it potential, and positive impact on our profession.
Focusing software education on engineering
Authors: Knight John C.
Published: November 2005

The software crisis is still with us. In fact, it is worse than it has ever been, and we see evidence of the crisis regularly. All manner of applications from desktop systems to large-scale information systems are delivered late, exceed their projected budgets, and fail in various ways leading to inconvenience, loss of service, and loss of revenue. A recent study by the National Institute of Standards and Technology found that software errors cost the U.S. Economy about $59.5 billion annually [4] National Institute of Standards and Technology, The Economic Impacts of Inadequate Infrast].
It's our job to care for SE
Authors: Wing Michael
Published: November 2005

I want software engineering to become a great and enduring profession. Alas, this topic is too large for one essay, so here I focus on the notion that "it is our job to care for SE." This can be restated as "we must be true to ourselves" or "success" comes from within" or "we are responsible for our own success." I believe that most of what I write here is obvious, but I believe it warrants a closer look and I want to say it clearly.
Surfing the net for software engineering notes
Authors: Doernhoefer Mark
Published: November 2005

What is good code? A simple question, but how can you tell if a load o' code is good stuff or a pile of spaghetti? That's where source code quality analysis comes into play. In this month's column, we're going to visit some web sites that will help you establish or improve your code quality processes.
Risks to the Public
Authors: Neumann Peter G.
Published: November 2005

Edited by Peter G. Neumann (Risks Forum Moderator and Chairman of the ACM Committee on Computers and Public Policy), plus personal contributions by others, as indicated. Opinions expressed are individual rather than organizational, and all of the usual disclaimers apply. We address problems relating to software, hardware, people, and other circumstances relating to computer systems. To economize on space, we include pointers to items in the online Risks Forum: (R i j) denotes RISKS vol i number j. Cited RISKS items generally identify contributors and sources, together with URLs. O cial RISKS archives are available at www.risks.org (which redirects to Newcastle and gets you nice html formatting and a search engine courtesy of Lindsay Marshall: http://catless.ncl.ac.uk/Risks/i.j.html gets you (R i j)) and at ftp://www.sri.com/risks.
Why quality?
Authors: Bhatti Shahid Nazir
Published: November 2005

The widespread use of information services will only be accepted by users if their quality is of acceptable level. It is therefore of high interest to be able to estimate, or even measure the quality of a system under construction. UML is now a de-factor standard for modelling systems to be build. This paper indicates how UML diagrams are related to software quality metrics as described in ISO/IEC 9126 and similar quality standards. The paper discusses relevant quality metrics, analyses sources of errors and relates them to the UML diagrams used in software engineering.The paper discusses the sub-attributes of the attribute 'Functionality' in more detail and relates the to the relevant UML diagrams.
Combinatorial completion by rule definition with interactive value colouring
Authors: Breen Michael
Published: November 2005

The combinatorial completion problem arises where one wishes to define a set of rules which collectively address all possible combinations of circumstances, as, for example, in a decision table. After some rules have been defined but, e.g., millions of cases remain to be addressed, how can the specifier best be helped to complete the remaining rules so that they cover every possible scenario? A novel technique is described based on providing interactive feedback to the user during rule definition. This can be used with non-tabular as well as tabular rules. Where previously quality would have depended on essentially sample-based approaches like testing, this technique makes it easy to adopt a rigorously complete approach to considering large numbers of possibilities.
A brief survey of program slicing
Authors: Xu Baowen , Qian Ju , Zhang Xiaofang , Wu Zhongqiang , Chen Lin
Published: November 2005

Program slicing is a technique to extract program parts with respect to some special computation. Since Weiser first proposed the notion of slicing in 1979, hundreds of papers have been presented in this area. Tens of variants of slicing have been studied, as well as algorithms to compute them. Different notions of slicing have different properties and different applications. These notions vary from Weiser's syntax-preserving static slicing to amorphous slicing which is not syntax-preserving, and the algorithms can be based on dataflow equations, information-flow relations or dependence graphs.Slicing was first-developed to facilitate debugging, but it is then found helpful in many aspects of the software development life cycle, including program debugging, software testing, software measurement, program comprehension, software maintenance, program parallelization and so on.Over the last two decades, several surveys on program slicing have been presented. However, most of them only reviewed parts of researches on program slicing or have now been out of date. People who are interested in program slicing need more information about the up to date researches. Our survey fills this gap. In this paper, we briefly review most of existing slicing techniques including static slicing, dynamic slicing and the latest slicing techniques. We also discuss the contribution of each work and compare the major difference between them. Researches on slicing are classified by the research hot spots such that people can be kept informed of the overall program slicing researches.
Review of "Balancing Agility and Discipline: A Guide for the Perplexed by Barry Boehm and Richard Turner"; Addison Wesley, 2004, ISBN 0-321-18612-5
Authors: Beasley Charles
Published: November 2005

Balancing Agility and Discipline: A Guide for the Perplexed
is a book written for the developers who live it the world caught between two conflicting approaches to software development, the Agile method and the Traditional methods. This book breaks out the basic reading to the main text and puts the technical material in the appendices. It also provides "fast track" summaries, side bar discussions, and margin notes. The book overall is organized to define the boundaries of the two methods followed by a chapter discussing where each method work the best. The next chapter covers the way a day might go using each method followed by a chapter describing two project cases. Chapter five gives a way to determine how to choose one method over the other with the final chapter giving you a summery of the material. Discussion, technical background and notes follow this.
Review of "Object Thinking by David West"; Microsoft Press: Microsoft, © 2004, 0-7356-1965-4
Authors: Che Haoyang
Published: November 2005

Object Thinking
, by David West, a highly renowned technologist and evangelist in the community, is definitely a thoughtful and profound object-oriented book. It is written in a really unique style, and different from other object books we've seen ever before. Previously, none of them shows too much interest in the cultural, historical, and philosophical underpinnings of objects in software development. This exceptional and controversial book begins with the basic premise that there is much more to object-oriented paradigm than a matter of experience of object-oriented languages. To fully understand object orientation requires understanding the philosophical and historical roots from which objects come. In a sense, the book talks more about knowledge instead of techniques, wisdom instead of knowledge.
Review of "The Elements of C++ Style by Trevor Misfeldt, Gregory Bumgardner, and Andrew Gray"; Cambridge University Press: Cambridge, ©2004, 0-521-89308-9
Authors: Che Haoyang
Published: November 2005

When we first write an article, generally speaking, we may not pay a lot of attention to the style. However, after a few more pieces, we will gradually find that these articles need polishing not only in the contents, but also in the styles, so we turn to Struck and White's
The Elements of Style
for help. Similarly, in the field of computer languages, there have many books (
The Elements of Java Style, The Elements of C++ Style, The Elements of UML Style
) furnishing a set of rules for writing in a certain language like C++ or Java. To some extent, conforming to style is a symbol of specialty. Consistent style facilitates communication and will be honored by other members in the same team.
Review of "Object-Oriented Programming with Visual Basic.NET by Michael McMillan"; Cambridge University Press: Cambridge, ©2004, 0-521-53983-8
Authors: Che Haoyang
Published: November 2005

I've already been a VB user for almost seven years. However, I must confess that I've rarely touched it since the last multimedia medical project. We used VB 6 in our development team, for that VB.NET didn't gain ground at that time. The first time I heard of VB.NET was in mid-2002. Then all of a sudden when I got up in the next morning, Microsoft .NET technology seemed to have become popular overnight. Buzzwords and slogans were everywhere: on the Internet, on the weighty books of published abstracts, on T-shirts, on sweatshirts, and even on souvenir pens. Is VB.NET still VB? Everyone may bear the question in his mind when he first glimpses at it.
Object-Oriented Programming with Visual Basic.NET
by Michael McMillan will give you a reasonable answer.
Review of "Testing Embedded Software by Bart Broekman and Edwin Notenboom"; Addison Wesley.; 2003
Authors: Ben-Menachem Mordechai
Published: November 2005

This book discusses testing of software and software-rich systems; particularly those that are embedded in larger Hardware/Software systems. On the other hand, to describe it another way, this book is one of those books that make writing book reviews really fun and worthwhile. (If that sounds like I like the book, you are right!) I have looked at just about every testing book to come out since Glenford Myers' '
The Art of Software Testing
' in 1979 (I have most of them, too; having caught acute bibliophilia at an early age). This is clearly one of the better ones in quite a while; at least since Boris Beizer, and that is saying a lot.
Review of "Find the Bug: A Book of Incorrect Programs by Adam Barr"; Pearson Education, 2004, ISBN 0321223918
Authors: Saur Joe
Published: November 2005

Now, this is a real geek's book! Most of us would rather
write code
than
read code
, but all of us have had to spend hours (or days!) hunting for the elusive bug that's driving us crazy, and this book offers the opportunity to develop and refine our bug-finding skills. What a concept!
On the definition of "on-line" in job scheduling problems
Authors: Feitelson Dror G. , Mu'alem Ahuva W.
Published: November 2005

The conventional model of on-line scheduling postulates that jobs have non-trivial release dates, and are not known in advance. However, it fails to impose any stability constraints, leading to algorithms and analyses that must deal with unrealistic load conditions arising from trivial release dates as a special case. In an effort to make the model more realistic, we show how stability can be expressed as a simple constraint on release times and processing times. We then give empirical and theoretical justifications that such a constraint can close the gap between the theory and practice. As it turns out, this constraint seems to trivialize the scheduling problem.
The halting problem on finite and infinite computers
Authors: Ylikoski Antti
Published: November 2005

This paper discusses some points originally raised by Robert L. Massey of Colorado, USA, and some consequences of that discussion. Firstly, earthly (ie. realistic) computers are finite because the number of atoms on Earth is finite. Secondly, and the main result of the paper is that, the famous Halting Problem is unsolvable only for infinite machines. In the end of the paper there are some thoughts about the consequences of these results, such as a suggestion to improve the classical Linear Bounded Automaton model.
Joint review of "Introduction To Natural Computation by Dana H. Ballard"; MIT Press, 1997, ISBN 0-262-52258-6 and "Mathematical Methods in Artificial Intelligence by Edward A. Bender", IEEE Press, 1996 ISBN 0-8186-7200-5.
Authors: Moss Lawrence S.
Published: November 2005

One of the interesting trends in theoretical computer science in recent years is the turn towards new application areas. It is not strange to see career shifts from complexity theory to cryptography, from type theory to security, from formal language theory to computational biology. The trend is reflected in journals as well. For example, the newly-open-for-business electronic journal
Logical Methods in Computer Science
has editors in the "emerging topics" of quantum computation and logic, and in computational systems in biology.
Theoretical Computer Science
recently added to its two sections (algorithms, automata, complexity and games; and logic, semantics and theory of programming) a third section entitled "Natural Computing". This "is devoted to the study of computing occurring in nature and computing inspired by nature. ... it will contain papers dealing with the theoretical issues in evolutionary computing, neural networks, molecular computing, and quantum computing." (Interstingly, SIGACT News seems to be immune from this trend, at least so far.) Finally, we turn from official journals to decidedly unofficial sources: weblogs summaries of panel discussions at conferences. On May 14, 2004, the Columbia/IBM Research/NYU Theory Day held a panel on "The Future of CS Theory." As reported in Lance Fornow's Computational Complexity Web Log, Richard Karp "highlighted three areas of interest for the future: (1) the study of large scale distributed systems such as the Web, incorporating ideas from economics and game theory; (2) connections with areas of natural science, ranging from statistical physics to quantum mechanics to biology; and (3) the 'new face' of AI in which stochastic and graphical models and statistical inference are playing a big role."
Guest Column: NP-complete problems and physical reality
Authors: Aaronson Scott
Published: November 2005

Can NP-complete problems be solved efficiently in the physical universe? I survey proposals including soap bubbles, protein folding, quantum computing, quantum advice, quantum adiabatic algorithms, quantum-mechanical nonlinearities, hidden variables, relativistic time dilation, analog computing, Malament-Hogarth spacetimes, quantum gravity, closed timelike curves, and "anthropic computing." The section on soap bubbles even includes some "experimental" results. While I do not believe that any of the proposals will let us solve NP-complete problems efficiently, I argue that by studying them, we can learn something not only about computation but also about physics.
Three dozen papers on online algorithms
Authors: Jawor Wojciech
Published: November 2005

This column contains a summary of last year's research on online algorithms presented at the STOC, FOCS, ICALP, ESA, and STACS conferences. Unfortunately, due to space constraints, the report could not be entirely exhaustive, and results from other conferences or journal articles are not covered. We hope that all readers will find in the survey something of interest, to fill those long winter evenings. The papers in the report are organized roughly by applications.
Implementing aggregation and broadcast over Distributed Hash Tables
Authors: Li Ji , Sollins Karen , Lim Dah-Yoh
Published: November 2005

Peer-to-peer (P2P) networks represent an effective way to share information, since there are no central points of failure or bottleneck. However, the flip side to the distributive nature of P2P networks is that it is not trivial to aggregate and broadcast global information efficiently. We believe that this aggregation/broadcast functionality is a fundamental service that should be layered over existing Distributed Hash Tables (DHTs), and in this work, we design a novel algorithm for this purpose. Specifically, we build an aggregation/broadcast tree in a bottom-up fashion by mapping nodes to their parents in the tree with a
parent function.
The particular parent function family we propose allows the efficient construction of multiple interior-node-disjoint trees, thus preventing single points of failure in tree structures. In this way, we provide DHTs with an ability to collect and disseminate information efficiently on a global scale. Simulation results demonstrate that our algorithm is efficient and robust.
An empirical evaluation of internet latency expansion
Authors: Zhang Hui , Goel Ashish , Govindan Ramesh
Published: November 2005

The Internet's latency expansion determines the asymptotic performance of large-scale distributed systems (such as Peer-to-Peer systems), but previous studies on the Internet have defined expansion in terms of
router-level hops.
In this paper, we empirically determine the Internet's latency expansion characteristics using measurements from two different Internet topology datasets. Our results show that the Internet router-level topology exhibits a
power-law
latency expansion, in contrast to its
exponential
expansion rate in terms of hops.
A new methodology for representation of TCP performance in multiconnection environments
Authors: González-Parada Eva , Cano-García J. M. , Díaz-Estrella A.
Published: November 2005

This paper presents a new methodology for graphical representation of TCP performance, either in simulation or real tests, for scenarios where many connections carrying different amounts of data coexist simultaneously. The methodology is based on statistical evaluation of the connections' goodput and graphical representation of the results using three plotting styles, each optimized for a different analysis. The suitability of this methodology has been proven by analysing the performance of different TCP versions and configurations in a web-browsing simulated scenario.
Back to the future part 4
Authors: Lam Simon S.
Published: November 2005

I thank the SIGCOMM Awards committee for this great honor. I would like to share this honor with my former and current students, and colleagues, who collaborated and co-authored papers with me. Each one of them has contributed to make this award possible. To all my coauthors, I thank you.
Observations of IPv6 traffic on a 6to4 relay
Authors: Savola Pekka
Published: November 2005

FUNET has been operating a public, globally-used 6to4 (RFC 3056) relay router since November 2001. The traffic has been logged and is now analyzed to gather information of 6to4 and IPv6 deployment.Among other figures, we note that the number of 6to4 capable nodes has increased by an order of magnitude in half a year: in April 2004, there are records of about 2 million different 6to4 nodes using this particular relay. Vast majority of this is just testing the availability of the relay, done by the Microsoft Windows systems, but the real traffic has also increased over time.While the observed 6to4 traffic has typically consisted of relatively simple system-level applications, or applications by power users, the emergence of peer-to-peer applications such as BitTorrent was also observed.
Collecting the internet AS-level topology
Authors: Zhang Beichuan , Liu Raymond , Massey Daniel , Zhang Lixia
Published: November 2005

At the inter-domain level, the Internet topology can be represented by a graph with Autonomous Systems (ASes) as nodes and AS peerings as links. This AS-level topology graph has been widely used in a variety of research efforts. Conventionally this topology graph is derived from routing tables collected by Route Views or RIPE RIS. In this work, we assemble the most complete AS-level topology by extending the conventional method along two dimensions. First, in addition to using data from RouteViews and RIPE RIS, we also collect data from many other sources, including route servers, looking glasses, and routing registries. Second, in addition to using routing tables, we also accumulate topological information from routing updates over time. The resulting topology graph on a recent day contains 44% more links and 3% more nodes than that from using RouteViews routing tables alone. Our data collection and topology generation process have been automated, and we publish the latest topology on the web on a daily basis.
Computer science and the mathematics genealogy project
Authors: Coonce Harry B.
Published: November 2005

From the book of Genesis to the TCS genealogy of Ian Parberry [1] folks have been inquisitive about their roots. In academic disciplines --- such as computer science, mathematics, statistics, etc. --- people are frequently interested in their academic heritage.
Review of "Boolean Functions and Computation Models by Peter Clote and Evangelos Kranakis", Springer-Verlag, 2002
Authors: Taylor R. Gregory
Published: November 2005

This wide-ranging monograph covers a number of research areas including Boolean functions and Boolean circuit families, propositional proof systems, sequential and parallel models of computation, and function algebras. If anything links them all together, it is surely complexity.
Review of "Selected Papers in Discrete Mathematics by D. Knuth", CSLI (Center for the Study of Language and Information Publication) paperback, $72.00
Authors: Oliveira Carlos A. S.
Published: November 2005

The book "Selected Papers in Discrete Mathematics" is a compilation of work published (plus some unpublished papers) by Donald E. Knuth, in the area of discrete mathematics. Clearly, the author does not need any introduction, and is well known by his authoritative work in areas such analysis of algorithms and digital typography. However, more than this, Knuth is a great example of good expositor and writer. Thus, even if your interests are not directly related to the more mathematical areas of computer science, it is greatly rewarding to read this book as a way of learning how to write good papers.
The computation of market equilibria
Authors: Codenotti Bruno , Pemmaraju Sriram , Varadarajan Kasturi
Published: November 2005

The market equilibrium problem has a long and distinguished history. In 1874, Walras published the famous "Elements of Pure Economics", where he describes a model for the state of an economic system in terms of demand and supply, and expresses the
supply equals demand
equilibrium conditions [62]. In 1936, Wald gave the first proof of the existence of an equilibrium for the Walrasian system, albeit under severe restrictions [61]. In 1954, Nobel laureates Arrow and Debreu proved the existence of an equilibrium under milder assumptions [3]. This existence result, along with the two fundamental theorems of welfare are the pillars of modern equilibrium theory.
The First Fundamental Theorem of Welfare
showed the Pareto optimality of allocations at equilibrium prices, thereby formally expressing Adam Smith's "invisible hand" property of markets and providing important social justification for the theory of equilibrium.
ACM SIGACT news distributed computing column 16
Authors: Rajsbaum Sergio
Published: November 2005

The Distributed Computing Column covers the theory of systems that are composed of a number of interacting computing elements. These include problems of communication and networking, databases, distributed shared memory, multiprocessor architectures, operating systems, verification, Internet, and the Web.
Coordination mechanisms for congestion games
Authors: Chrobak Marek , Koutsoupias Elias
Published: November 2005

Recently there has been a lot of interest in problems at the intersection of Game Theory, Economics, and Computer Science. For example, there are interesting developments concerning algorithms for equilibria and cost sharing, algorithmic mechanism design, and the efficiency of systems with selfish users [25]. In this note, I will focus on the last area and in particular on the price of anarchy of task allocation, selfish routing, and congestion games. I will discuss the issues of this area, mention the central results, and suggest some open problems, some of them close in spirit to competitive analysis.
The atomic manifesto
Authors: Jones Cliff , Lomet David , Romanovsky Alexander , Weikum Gerhard , Fekete Alan , Gaudel Marie-Claude , Korth Henry F. , de Lemos Rogerio , Moss Eliot , Rajwar Ravi , Ramamritham Krithi , Randell Brian , Rodrigues Luis
Published: November 2005

This paper is based on a five-day workshop on "Atomicity in System Design and Execution" that took place in Schloss Dagstuhl in Germany [5] in April 2004 and was attended by 32 people from different scientific communities. The participants included researchers from the four areas of• database and transaction processing systems,• fault tolerance and dependable systems,• formal methods for system design and correctness reasoning, and• to a smaller extent, hardware architecture and programming languages.
The classification of deadlock prevention and avoidance is erroneous
Authors: Levine Gertrude Neuman
Published: November 2005

Mechanisms to control resource deadlock are frequently classified as prevention or avoidance schemes. The prevention schemes are listed as those that directly negate the necessary preconditions of resource deadlock. The avoidance schemes, although they obviously also prevent deadlock, are described as not addressing the preconditions for the occurrence of deadlock.We claim that this classification is erroneous. Typically, the necessary preconditions for resource deadlock that are provided are incomplete. Once all of the preconditions are examined, it is obvious that "deadlock avoidance" does indeed negate a precondition.
Modeling VP operation
Authors: Joshi Rushikesh K. , Rajaa Subash
Published: November 2005

A new higher-level synchronization problem called
Diwali Festival Problem
(DFP) is presented. The problem captures the requirements for implementing the VP operation for semaphores outside the operating system kernel in presence of P and V operations, and shared variables with atomic reads and writes.
Thread coloring
Authors: Gil Marisa , Pinilla Ruben
Published: November 2005

The appearance of simultaneous multithreading (SMT) processors, offering instruction-level parallelism and increasing hardware resources utilization, permits the execution of various instructions streams at the same time. A particular case is the Intel SMT implementation (Hyper-Threading Technology) where a processor can execute two instructions streams independently. Due to hardware resources sharing in a Hyper-Threading processor, both instruction streams can contend for the same execution resources depending on the instruction execution units utilization.As other works in this area have demonstrated, we have observed that the system throughput can be improved when the execution resources used by each thread are contemplated in their scheduling. Starting from the evaluation results, we propose a Thread Coloring philosophy that designs a way to manage information about resources utilization (hardware and software resources) per each thread. This policy permits the scheduler to select threads that will perform better with less resource contention, besides including OS upper layers in the resource management. The proposed Thread Coloring scheme establishes the bases of processor and OS cooperation, sharing resources utilization information and providing a form of controlling logical processor thread assignment taking into account possible resource contention.
A new pattern for flexible worker threads with in-place consumption message queues
Authors: Steinke Robert , Clark Micah , McMahon Elihu
Published: November 2005

We present a new pattern for implementing worker threads that is more flexible than traditional patterns. Traditional worker threads receive command messages with enumerated IDs that refer to pre-defined behaviors. In our new pattern, worker threads receive function pointers, and they have only one behavior: invoke the function. In this way, new behaviors can be passed in to the thread at run-time rather than having to be pre-defined. In addition, we present in-place consumption as an improvement for command message queues that reduces the number of times data needs to be copied.
ARC based superpaging
Authors: Wiseman Yair
Published: November 2005

This paper explores the use of the ARC algorithm for swapping policy in superpaging systems. The different page sizes can affect the algorithm and as a result the algorithm will not be as effective as the original one for traditional paging systems. We suggest to modify the threshold of the ARC algorithm, so it will give more weight to the frequently accessed pages and less weight to the recent pages.
A study of initialization in Linux and OpenBSD
Authors: Dodge Catherine , Irvine Cynthia , Nguyen Thuy
Published: November 2005

The code that initializes a system can be notoriously difficult to understand. In secure systems, initialization is critical for establishing a starting state that is secure. This paper explores two architectures used for bringing an operating system to its initial state, once the operating system gains control from the boot loader. Specifically, the ways in which the OpenBSD and Linux operating systems handle initialization are dissected.
Security in autonomic computing
Authors: Chess David M.
Published: November 2005

Over the last fifteen years the world has experienced a wide variety of computer virus and general computer security problems, against which a wide variety of countermeasures have been deployed. The record tells us that what most strongly determines the size and nature of the worldwide virus and security problem is not any particular countermeasure or security technology, but rather the characteristics of the underlying platform (the operating system, macro execution environment, and so on). Autonomic computing is a new effort, intended to make IT systems more self-managing. Since it undertakes to change the nature of the underlying computing platform, it is likely to change the size and nature of the world's virus and security problem as well. This paper briefly describes both the relevant historical record and some current architectural approaches to autonomic computing, and offers a few thoughts on how autonomic computing relates to computer security and virus prevention.
Towards the issues in architectural support for protection of software execution
Authors: Shi Weidong , Lee Hsien-Hsin S. , Lu Chenghuai , Ghosh Mrinmoy
Published: November 2005

Recently, there is a growing interest in the research community to employ tamper-resistant processors for software protection. Many of these proposed systems rely on a specially tailored secure processor to prevent 1) illegal software duplication, 2) unauthorized software modification, and 3) unauthorized software reverse engineering. Most of these works primarily focus on the feasibility demonstration and design details rather than trying to elucidate many fundamental issues that are either "elusive" or "confusing" to the architecture researchers. Furthermore, many proposed systems have been built on assumptions whose security implications have not been well studied or understood. Instead of proposing yet another new secure architecture model, in this paper, we will try to answer some of these fundamental questions with respect to using hardware-based cryptography for protecting software execution. Those issues include, 1) Is hardware cryptography necessary? 2) Is per-process single cryptography key enough to provide the flexibility, inter-operability, and compatibility required by today's complex software system? 3) Is OTP (one-time-pad) in combination with "lazy" authentication secure enough to protect software confidentiality? 4) Is there way to protect software integrity using less hardware resource? Finally, the paper defines the difference between off-line and on-line attacks and presents a very low overhead security enhancement technique that can improve protection on software integrity over on-line attacks by several magnitudes.
Memory predecryption
Authors: Rogers Brian , Solihin Yan , Prvulovic Milos
Published: November 2005

Memory encryption has become a common approach to providing a secure processing environment, but current schemes suffer from extra performance and storage overheads. This paper presents predecryption as a method of providing this security with less overhead by using well-known prefetching techniques to retrieve data from memory and perform decryption before it is needed by the processor. Our results, tested mostly on SPEC 2000 benchmarks, show that using our predecryption scheme can actually result in no increase in execution time despite an extra 128 cycle decryption latency per memory block access.
The case for crypto protocol awareness inside the OS kernel
Authors: Burnside Matthew , Keromytis Angelos D.
Published: November 2005

Separation of control and data plane is a principle increasingly used to improve the performance of network protocols and applications, such as the Web. Use of security mechanisms, such as the SSL/TLS protocol, can negate these performance gains, since such mechanisms need to be located on the data path. We argue that the same principle of separation can be applied to security mechanisms, by removing the web server from the secure data path.We present a
minimal
operating system extension that can improve the performance of web servers using SSL/TLS by up to 27%. Our intuition is that protocol framing and cryptographic transforms can be applied to incoming and outgoing data frames by the operating system under a policy specified by the web server. In this way, we can reduce the number of system calls and context switches to a small constant number, and the amount of data copying that involves the web server by 100%. We describe our prototype implementation for the OpenBSD operating system and quantify its performance implications.
Using DISE to protect return addresses from attack
Authors: Corliss Marc L. , Lewis E. Christopher , Roth Amir
Published: November 2005

Stack-smashing by buffer overflow is a common tactic used by viruses and worms to crash or hijack systems. Exploiting a bounds-unchecked copy into a stack buffer, an attacker can---by supplying a specially-crafted and unexpectedly long input---overwrite a stored return address and trigger the execution of code of her choosing. In this paper, we propose to protect code from this common form of attack using dynamic instruction stream editing (DISE), a previously proposed hardware mechanism that implements binary rewriting in a transparent, efficient, and convenient way by rewriting the dynamic instruction stream rather than the static executable. Simply, we define productions (rewriting rules) that instrument program calls and returns to maintain and verify a "shadow" stack of return addresses in a protected region of memory. When invalid return addresses are detected, the application is terminated.The DISE implementation resembles previous software schemes like StackGuard and the Return Address Defender (RAD), but it can operate without source code and in dynamically-linked libraries and dynamically-generated code. It also has natural facilities for protecting the shadow stack, which provides little security if it itself is vulnerable. Finally, unlike software instrumentation, DISE checks---which are inserted by the processor at runtime---cannot be bypassed or subverted.
A reliable return address stack
Authors: Ye Dong , Kaeli David
Published: November 2005

Buffer overflow vulnerability is one of the most common security bugs existing in today's software systems. In this paper, we propose a microarchitectural design of a return address stack aiming to detect and stop stack smashing. This approach has been used in other proposals to guard against buffer overflow vulnerabilities. Our contribution is a design that handle multipath execution, speculative execution, abnormal control flow, and extended call depth. Our solution makes no assumption about the presence of architecturally visible calls and returns.
Characterizing antivirus workload execution
Authors: Uluski Derek , Moffie Micha , Kaeli David
Published: November 2005

Despite the pervasive use of anti-virus (AV) software, there has not been a systematic study of the characteristics of the execution of this workload. In this paper we present a characterization of four commonly used anti-virus software packages. Using the Virtutech Simics toolset, we profile the behavior of four popular anti-virus packages as run on an Intel PentiumIV platform running Microsoft Windows-XP.In our study, we focus on the overhead introduced by the anti-virus software during
on-access
execution. The overhead associated with anti-virus execution can dominate overall performance. The AV-Test group has already reported that this overhead can range from 23-129% on live systems running
on-access
experiments [3].
1
The performance impact of the anti-virus execution is clearly an important issue, and we present the first quantitative study of the characteristics of this workload. Our study includes the impact of both operating system execution and system call execution.
Configurable string matching hardware for speeding up intrusion detection
Authors: Aldwairi Monther , Conte Thomas , Franzon Paul
Published: November 2005

Signature-based Intrusion Detection Systems (IDSs) monitor network traffic for security threats by scanning packet payloads for attack signatures. IDSs have to run at wire speed and need to be configurable to protect against emerging attacks. In this paper we consider the problem of string matching which is the most computationally intensive task in IDS. A configurable string matching accelerator is developed with the focus on increasing throughput while maintaining the configurability provided by the software IDSs. Our preliminary results suggest that the hardware accelerator offers an overall system performance of up to 14Gbps.
Architectural support for protecting user privacy on trusted processors
Authors: Zhang Youtao , Yang Jun , Lin Yongjing , Gao Lan
Published: November 2005

Recently proposed trusted processor model is a promising model for building secure applications. While effective designs have been proposed for protecting data confidentiality and data integrity in such environments, an important security criterion -- user privacy is usually neglected in current designs. Due to the increasing concern of privacy protection in the Internet era, such deficiency can hinder the adoption of the new model.In this paper, we identify the threat model to user privacy and propose a new scheme for user privacy protection. In addition to providing the same ability in protecting data confidentiality and data integrity, the new scheme effectively protects user privacy and only introduces very low overhead.
An architecture for elliptic curve cryptograph computation
Authors: Shirase Masaaki , Hibino Yasushi
Published: November 2005

It is known that several public key cryptosystems such as RSAs, ElGamals and elliptic curve cryptosystems [1], and also elliptic curve cryptosystems require smaller keys and more efficient operation than RSAs and ElGamals for same security. For example, elliptic curve cryptosystems with 160 bits key have same security as RSAs and ElGamals with 1024 bits key have. We focus elliptic curve cryptosystems and propose an architecture of computation unit for an elliptic curve cryptosystem with small hardware.
Fault tolerant bus architecture for deep submicron based processors
Authors: Venkateswaran N. , Balaji S. , Sridhar V.
Published: November 2005

In the Deep Submicron era testing of processors is gaining prominence due to the effect of many analog faults. These faults have a direct impact on the signal integrity in interconnects. In deep submicron based processors electromigration poses a major challenge for interconnect reliability. This is of major concern in processor bus architectures. Though a lot of research has been focused on fault tolerance at the module level, no effective research has been carried out to evolve fault tolerant interconnect structures. Faults due to electromigration give rise to weak ones and zeros, thus affecting the signal integrity. This paper presents a fault tolerant scheme for electromigration which also leads to unification of detection and correction of crosstalk faults and stuck-at faults. In the scheme presented, the signal is rerouted through adjacent spare interconnects. The spare interconnect also acts as a shield against crosstalk under fault free system operation. Moreover, the entire testing process is carried out concurrently with the processor instruction execution. The hardware overhead is also insignificant compared to the overall device count in a deep submicron based processor. To the best of our knowledge this is the first time a fault tolerant scheme for bus architectures is being presented.
Educating software engineers
Authors: Reifer Donald J.
Published: November 2005

When Peter Henderson asked me to comment on the software engineering curricula proposed by the IEEE and ACM Joint Task Force
1
, I was thrilled. I thought the idea of academics asking for industry input to be strikingly original. I then dug into the proposed curriculum to determine if it would help prepare those from academia entering the software engineering workforce with the skills, knowledge and abilities they need to build quality software products on-time and within budget. Software engineers in most industrial organizations are problem solvers who perform difficult tasks like interfacing with users, developing requirements, specifying interfaces, performing design tradeoffs, developing algorithms and testing and evaluating products. They must be able to communicate with others from associated engineering disciplines, like communications and systems engineering, and work as members of interdisciplinary teams.
Toward a great and enduring profession
Authors: Wing Michael
Published: November 2005

SE is emerging from years of turmoil. Practitioners are beginning to stand up for themselves and their profession. I have seen them do so in Technology Review and heard them on NPR. Practitioners are fighting for their jobs, against outsourcers, like the SEI.