Secure Xenix™ is an experimental system designed to run on IBM PC/AT workstations. Like Xenix, it is a Unix™ System V implementation on the PC/AT workstation; unlike Xenix, it eliminates the Unix security deficiencies and it enhances security policies. In this paper, we present the design features of Secure Xenix, their integration within Xenix, and some of the lessons learned from this experiment to date.

Secure Xenix * is an experimental system designed to run on IBM PC/AT workstations. Like Xenix, it is a Unix implementation on the PC/AT workstation; unlike Xenix, it eliminates the Unix security deficiencies and it enhances security policies. In this paper, we present the design features of Secure Xenix, their integration within Xenix, and some of the lessons learned from this experiment to date. In addition, we address some of the problems specific to workstations in the security management area. The major design differences between Secure Xenix and other experiments with Unix security enhancements, such as LINUS IV, are also presented. In a companion paper, we present the important problems that arise in the testing of Secure Xenix and their solutions.

We describe and prove correct a programming technique using a linked list of pages for managing the free disk pages of a file system where shadowing is the recovery technique. Our technique requires a window of only two pages of main memory for accessing and maintaining the free list, and avoids wholesale copying of free-list pages during a checkpoint or recover operation.

Several polynomial time approximation algorithms for some $NP$-complete routing problems are presented, and the worst-case ratios of the cost of the obtained route to that of an optimal are determined. A mixed-strategy heuristic with a bound of 9/5 is presented for the stacker-crane problem (a modified traveling salesman problem). A tour-splitting heuristic is given for k-person variants of the traveling salesman problem, the Chinese postman problem, and the stacker-crane problem, for which a minimax solution is sought. This heuristic has a bound of $e + 1 - 1/k$, where e is the bound for the corresponding 1-person algorithm.

Several polynomial time approximation algorithms for some NP-complete routing problems are presented, and the worst-case ratios of the cost of the obtained route to that of an optimal are determined. A mixed-strategy heuristic with a bound of 9/5 is presented for the Stacker-Crane problem (a modified Traveling Salesman problem). A tour-splitting heuristic is given for k-person variants of the Traveling Salesman problem, the Chinese Postman problem, and the Stacker-Crane problem, for which a minimax solution is sought. This heuristic has a bound of e + 1 - 1/k, where e is the bound for the corresponding 1-person algorithm.

A simple, iterative bit propagation algorithm for solving global data flow analysis problems such as “available expressions” and “live variables” is presented and shown to be quite comparable in speed to the corresponding interval analysis algorithm. This comparison is facilitated by a result relating two parameters of a reducible flow graph (rfg). Namely, if G is an rfg, d is the largest number of back edges found in any cycle-free path in G, and k is the length of the interval derived sequence of G, then $k \geqq d$. (Intuitively, k is the maximum nesting depth of loops in a computer program, while d is a measure of the maximum loop-interconnectedness.) The node ordering employed by the simple algorithm is the reverse of the order in which a node is last visited while growing any depth-first spanning tree of the flow graph. In addition, a dominator algorithm for an rfg is presented which takes O(edges) bit vector steps.

It is established that if G is a reducible flow graph, then edge ( n, m ) is backward (a back latch) if and only if either n = m or m dominates n in G . Thus, the backward edges of a reducible flow graph are unique. Further characterizations of reducibility are presented. In particular, the following are equivalent: (a) G = ( N, E, n 0 ) is reducible. (b) The “dag” of G is unique. (A dag of a flow graph G is a maximal acyclic flow graph which is a subgraph of G .) (c) E can be partitioned into two sets E 1 and E 2 such that E 1 forms a dag D of G and each ( n, m ) in E 2 has n = m or m dominates n in G . (d) Same as (c), except each ( n, m ) in E 2 has n = m or m dominates n in D . (e) Same as (c), except E 2 is the back edge set of a depth-first spanning tree for G . (f) Every cycle of G has a node which dominates the other nodes of the cycle. Finally, it is shown that there is a “natural” single-entry loop associated with each backward edge of a reducible flow graph.

There is an ordering of the nodes of a flow graph G which topologically sorts the dominance relation and can be found in 0(edges) steps. This ordering is the reverse of the order in which a node is last visited while growing any depth-first spanning tree of G. Moreover, if G is reducible, then this ordering topologically sorts the dag of G. Thus, for a reducible flow graph (rfg) there is a simple algorithm to compute the dominators of each node in 0(edges) bit vector steps.The main result of this paper relates two parameters of an rfg. If G is reducible, d is the largest number of back edges found in any cycle-free path in G, and k is the length of the interval derived sequence of G, then k≥d. From this result it follows that there is a very simple bit propagation algorithm (indeed, the obvious one) which also uses the above ordering, and is at least as good as the interval algorithm for solving all known global data flow problems such as available expressions and live variables.

The structure of programs can often be described by a technique called “interval analysis” on their flow graphs. Here, we characterize the set of flow graphs that can be analyzed in this way in terms of two very simple transformation on graphs. We then give a necessary and sufficient condition for analyzability and apply it to “goto-less programs,” showing that they all meet the criterion.

The structure of , programs can often be described by a technique called “interval analysis” on their flow graphs. Here, we characterize the set of flow graphs that can be analyzed in this way in terms of two very simple transformations on graphs. We then give a necessary and sufficient condition for analyzability and apply it to “goto-less programs,” showing that they all meet the criterion.