ScholarBank@NUShttps://scholarbank.nus.edu.sgThe DSpace digital repository system captures, stores, indexes, preserves, and distributes digital research material.Mon, 21 Oct 2019 12:57:16 GMT2019-10-21T12:57:16Z50791- Efficient algorithms for functional constraintshttps://scholarbank.nus.edu.sg/handle/10635/41972Title: Efficient algorithms for functional constraints
Authors: Zhang, Y.; Yap, R.H.C.; Li, C.; Marisetti, S.
Abstract: Functional constraints are an important constraint class in Constraint Programming (CP) systems, in particular for Constraint Logic Programming (CLP) systems. CP systems with finite domain constraints usually employ CSP-based solvers which use local consistency, e.g. arc consistency. We introduce a new approach which is based instead on variable substitution. We obtain efficient algorithms for reducing systems involving functional and bi-functional constraints together with other non-functional constraints. It also solves globally any CSP where there exists a variable such that any other variable is reachable from it through a sequence of functional constraints. Our experiments show that variable elimination can significantly improve the efficiency of solving problems with functional constraints. © 2008 Springer Berlin Heidelberg.
Tue, 01 Jan 2008 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/419722008-01-01T00:00:00Z
- A MapReduce-based maximum-flow algorithm for large small-world network graphshttps://scholarbank.nus.edu.sg/handle/10635/43220Title: A MapReduce-based maximum-flow algorithm for large small-world network graphs
Authors: Halim, F.; Yap, R.H.C.; Wu, Y.
Abstract: Maximum-flow algorithms are used to find spam sites, build content voting system, discover communities, etc., on graphs from the Internet. Such graphs are now so large that they have outgrown conventional memory-resident algorithms. In this paper, we show how to effectively parallelize a max-flow algorithm based on the Ford-Fulkerson method on a cluster using the MapReduce framework. Our algorithm exploits the property that such graphs are small-world networks with low diameter and employs optimizations to improve the effectiveness of MapReduce and increase parallelism. We are able to compute max-flow on a subset of the Facebook social network graph with 411 million vertices and 31 billion edges using a cluster of 21 machines in reasonable time. © 2011 IEEE.
Sat, 01 Jan 2011 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/432202011-01-01T00:00:00Z
- Optimizing compilation of CLP(R)https://scholarbank.nus.edu.sg/handle/10635/99368Title: Optimizing compilation of CLP(R)
Authors: Kelly, A.D.; Marriott, K.; Macdonald, A.; Stuckey, P.J.; Yap, R.
Abstract: Constraint Logic Programming (CLP) languages extend logic programming by allowing the use of constraints from different domains such as real numbers or Boolean functions. They have proved to be ideal for expressing problems that require interactive mathematical modeling and complex combinatorial optimization problems. However, CLP languages have mainly been considered as research systems, useful for rapid prototyping, but not really competitive with more conventional programing languages where efficiency is a more important consideration. One promising approach to improving the performance of CLP systems is the use of powerful program optimizations to reduce the cost of constraint solving. We extend work in this area by describing a new optimizing compiler for the CLP language CLP(R). The compiler implements six powerful optimizations: reordering of constraints, bypass of the constraint solver, splitting and dead-code elimination, removal of redundant constraints, removal of redundant variables, and specialization of constraints which cannot fail. Each program optimization is designed to remove the overhead of constraint solving when possible and keep the number of constraints in the store as small as possible. We systematically evaluate the effectiveness of each optimization in isolation and in combination. Our empirical evaluation of the compiler verifies that optimizing compilation can be made efficient enough to allow compilation of real-world programs and that it is worth performing such compilation because it gives significant time and space performance improvements.
Sun, 01 Nov 1998 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/993681998-11-01T00:00:00Z
- STR3: A path-optimal filtering algorithm for table constraintshttps://scholarbank.nus.edu.sg/handle/10635/127218Title: STR3: A path-optimal filtering algorithm for table constraints
Authors: Lecoutre, Christophe; Likitvivatanavong, Chavalit; Yap, Roland
Thu, 01 Jan 2015 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/1272182015-01-01T00:00:00Z
- Physical access protection using continuous authenticationhttps://scholarbank.nus.edu.sg/handle/10635/43360Title: Physical access protection using continuous authentication
Authors: Yap, R.H.C.; Sim, T.; Kwang, G.X.Y.; Ramnath, R.
Abstract: Traditional password based authentication systems assume that the user who manages to sign-on into the system is the actual authorized user. There is no differentiation between the authorized user and an intruder who knows how to signon into the system. This paper describes an authentication mechanism which reduces the risk of un-authorized system usage by continuously authenticating the current user. This is achieved by using biometric sensors which can verify the user in a transparent fashion. We have developed two such prototype systems - one for Linux, and the other for Windows - both of which are directly integrated with the operating system. This paper focuses on the Windows platform. The benefit of our continuous authentication system is that it gives a higher degree of assurance that the authorized user is indeed the one presently using the system, and does so in a way that is transparent to the user. Preliminary user studies on Windows demonstrate that continuous authentication can be used successfully on a user population using Windows on a variety of interactive applications which simulate a general task mix. Our studies show that the goal of transparency is achieved as most users were not bothered nor affected by presence of the continuous authentication system. ©2008 IEEE.
Tue, 01 Jan 2008 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/433602008-01-01T00:00:00Z
- A path-optimal GAC algorithm for table constraintshttps://scholarbank.nus.edu.sg/handle/10635/77972Title: A path-optimal GAC algorithm for table constraints
Authors: Lecoutre, C.; Likitvivatanavong, C.; Yap, R.H.C.
Abstract: Filtering by Generalized Arc Consistency (GAC) is a fundamental technique in Constraint Programming. Recent advances in GAC algorithms for extensional constraints rely on direct manipulation of tables during search. Simple Tabular Reduction (STR), which systematically removes invalid tuples from tables, has been shown to be a simple yet efficient approach. STR2, a refinement of STR, is considered to be among the best filtering algorithms for positive table constraints. In this paper, we introduce a new GAC algorithm called STR3 that is specifically designed to enforce GAC during search. STR3 can completely avoid unnecessary traversal of tables, making it optimal along any path of the search tree. Our experiments show that STR3 is much faster than STR2 when the average size of the tables is not reduced drastically during search. © 2012 The Author(s).
Sun, 01 Jan 2012 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/779722012-01-01T00:00:00Z
- An MDD-based generalized arc consistency algorithm for positive and negative table constraints and some global constraintshttps://scholarbank.nus.edu.sg/handle/10635/40290Title: An MDD-based generalized arc consistency algorithm for positive and negative table constraints and some global constraints
Authors: Cheng, K.C.K.; Yap, R.H.C.
Abstract: A table constraint is explicitly represented as its set of solutions or non-solutions. This ad hoc (or extensional) representation may require space exponential to the arity of the constraint, making enforcing GAC expensive. In this paper, we address the space and time inefficiencies simultaneously by presenting the mddc constraint. mddc is a global constraint that represents its (non-)solutions with a multi-valued decision diagram (MDD). The MDD-based representation has the advantage that it can be exponentially smaller than a table. The associated GAC algorithm (called mddc) has time complexity linear to the size of the MDD, and achieves full incrementality in constant time. In addition, we show how to convert a positive or negative table constraint into an mddc constraint in time linear to the size of the table. Our experiments on structured problems, car sequencing and still-life, show that mddc is also a fast GAC algorithm for some global constraints such as sequence and regular. We also show that mddc is faster than the state-of-the-art generic GAC algorithms in Gent et al. (2007), Lecoutre and Szymanek (2006), Lhomme and Régin (2005) for table constraint. © Springer Science+Business Media, LLC 2009.
Fri, 01 Jan 2010 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/402902010-01-01T00:00:00Z
- Many-to-many interchangeable sets of values in CSPshttps://scholarbank.nus.edu.sg/handle/10635/78220Title: Many-to-many interchangeable sets of values in CSPs
Authors: Likitvivatanavong, C.; Yap, R.H.C.
Abstract: Onto-substitutability has been shown to be intrinsic to how a domain value is considered redundant. A value is onto-substitutable if any solution involving that value remains a solution when that value is replaced by some other value. We redefine onto-substitutability to accommodate binary relationships and study its implication. Joint interchangeability, an extension of onto-substitutability to its interchangeabil-ity counterpart, emerges as one of the results. We propose a new way of removing interchangeable values by constructing a new value as an intermediate step, as well as introduce virtual interchangeability, a local reasoning that leads to joint interchangeability and allows values to be merged together. Copyright 2013 ACM.
Tue, 01 Jan 2013 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/782202013-01-01T00:00:00Z
- Solving functional constraints by variable substitutionhttps://scholarbank.nus.edu.sg/handle/10635/41627Title: Solving functional constraints by variable substitution
Authors: Zhang, Y.; Yap, R.H.C.
Abstract: Functional constraints and bi-functional constraints are an important constraint class in Constraint Programming (CP) systems, in particular for Constraint Logic Programming (CLP) systems. CP systems with finite domain constraints usually employ Constraint Satisfaction Problem(s)-based solvers which use local consistency, for example, arc consistency. We introduce a new approach which is based instead on variable substitution. We obtain efficient algorithms for reducing systems involving functional and bi-functional constraints together with other nonfunctional constraints. It also solves globally any CSP where there exists a variable such that any other variable is reachable from it through a sequence of functional constraints. Our experiments on random problems show that variable elimination can significantly improve the efficiency of solving problems with functional constraints. © 2011 Cambridge University Press.
Sat, 01 Jan 2011 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/416272011-01-01T00:00:00Z
- Applying Ad-hoc global constraints with the case constraint to still-lifehttps://scholarbank.nus.edu.sg/handle/10635/42197Title: Applying Ad-hoc global constraints with the case constraint to still-life
Authors: Cheng, K.C.K.; Yap, R.H.C.
Abstract: The Still-Life problem is challenging for CP techniques because the basic constraints of the game of Life are loose and give poor propagation for Still-Life. In this paper, we show how ad hoc global case constraints can be customized to construct various models to provide much stronger propagation with CP solvers. Since we use custom ad hoc constraints of high arity where the number of tuples to define the constraint are large, the actual constraint representation becomes important to avoid excessive space consumption. We demonstrate how to use BDDs to construct good representations for the case constraint which is critical for efficiency. Our results seem comparable to hybrid CP/IP models even though we are only using propagation albeit on ad hoc global constraints. This paper shows an extensive example of how to systematically build models using different kinds of ad hoc constraints. It also demonstrates the solving potential of ad hoc global constraints. © Springer Science + Business Media, LLC 2006.
Sun, 01 Jan 2006 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/421972006-01-01T00:00:00Z
- Security issues in small world network routinghttps://scholarbank.nus.edu.sg/handle/10635/40703Title: Security issues in small world network routing
Authors: Halim, F.; Wu, Y.; Yap, R.H.C.
Abstract: Small World Network (SWN) have been shown to be navigable - a short route can be found using efficiently using decentralized algorithms. This routing relies on nodes having a position to guide the routing such as its coordinates. Even in the absence of positional information such as node coordinates, by using local self-reorganization, it is possible to reconstruct a proxy for the node coordinates which still allows for efficient routing. This paper shows that in the presence of malicious nodes, the self-reorganization mechanism breaks down. We investigate self-protection mechanisms for such SWNs. Preliminary results using a simple restart mechanism for self-tuning shows that much of the effect of malicious nodes can be mitigated. © 2008 IEEE.
Tue, 01 Jan 2008 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/407032008-01-01T00:00:00Z
- Extending BAN logic for reasoning with modern PKI-based protocolshttps://scholarbank.nus.edu.sg/handle/10635/43233Title: Extending BAN logic for reasoning with modern PKI-based protocols
Authors: Sufatrio; Yap, R.H.C.
Abstract: BAN Logic is a well-known authentication logic which, despite other more recent logics and formal methods, remains popular with many protocol designers. BAN Logic however does not properly deal with the issues of certificates and the use of Public Key Infrastructure (PKI). This paper proposes an extension to BAN Logic which focuses on certificate processing within the PKI setting. Our extension is along the lines of the work by Gaarder and Snekkenes but better captures current aspects of PKI. In particular, our extension redresses the reasoning on the goodness of private keys, and considers certificate revocation. Common pitfalls in public-key based protocol design are due to insufficient attention placed on the "intended recipient" as well as the "stated sender" of a message. Our extension makes the recipient and sender explicit, which reduces the likelihood of introducing such flaws into the protocol and its subsequent proof using BAN Logic. In summary, our logic is primarily focused on making BAN Logic more concise yet practical to use on PKI-based protocols. © 2008 IEEE.
Tue, 01 Jan 2008 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/432332008-01-01T00:00:00Z
- A hierarchy of tractable subclasses for SAT and counting SAT problemshttps://scholarbank.nus.edu.sg/handle/10635/39934Title: A hierarchy of tractable subclasses for SAT and counting SAT problems
Authors: Andrei, Ş.; Grigoraş, G.; Rinard, M.; Chuan Yap, R.H.
Abstract: Finding subclasses of formulæ for which the SAT problem can be solved in polynomial time has been an important problem in computer science. We present a new hierarchy of propositional formulæ subclasses for which the SAT and counting SAT problems can be solved in polynomial time. Our tractable subclasses are those propositional formulæ in conjunctive normal form where any set of k + 1 clauses are related, i.e., there exists at least one literal in one clause that appears negated in another clause of the considered set of k + 1 clauses. We say this subclass of formulæ is of rank k and it is different from previously known subclasses that are solvable in polynomial time. This is an improvement over the SAT Dichotomy Theorem and the counting SAT Dichotomy Theorem, since our subclass can be moved out from the ℕℙ-complete class to the ℙ class. The membership problem for this new subclass can be solved in O(n · l k+1), where n, l and k are the number of variables, clauses and the rank (1 ≤ k ≤ l - 1), respectively. We give an efficient algorithm to approximate the number of assignments for any arbitrary conjunctive normal form propositional formula by an upper bound. © 2009 IEEE.
Thu, 01 Jan 2009 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/399342009-01-01T00:00:00Z
- Enhancing host security using external environment sensorshttps://scholarbank.nus.edu.sg/handle/10635/43136Title: Enhancing host security using external environment sensors
Authors: Chang, E.-C.; Lu, L.; Wu, Y.; Yap, R.H.C.; Yu, J.
Abstract: We propose a framework that uses (external) environment information to enhance computer security. The benefit of our framework is that the environment information is collected by sensors that are outside the control of a host and communicate to an external monitor via an out-of-band channel (w.r.t. the host), thus it cannot be compromised by malware on a host system. The information gathered still remains intact even if malware uses rootkit techniques to hide its activities. Our framework can be applied for a number of security applications: (1) intrusion detection; (2) rate monitoring/control of external resources; and (3) access control. We show that that the framework is useful even with coarse-grained and simple information. We present some experimental prototypes that employ the framework to detect/control email spam, detect/control DDoS zombie attacks and detect misuse of compute resources. Experimental evaluation shows that the framework is effecting in detecting or limiting the activities of such malware. The growing popularity of multimodal sensors and physical security information management systems suggests that such environmental sensors will become common making our framework cost effective and feasible in the near future. © 2011 Springer-Verlag.
Sat, 01 Jan 2011 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/431362011-01-01T00:00:00Z
- An optimal coarse-grained arc consistency algorithmhttps://scholarbank.nus.edu.sg/handle/10635/39294Title: An optimal coarse-grained arc consistency algorithm
Authors: Bessière, C.; Régin, J.-C.; Yap, R.H.C.; Zhang, Y.
Abstract: The use of constraint propagation is the main feature of any constraint solver. It is thus of prime importance to manage the propagation in an efficient and effective fashion. There are two classes of propagation algorithms for general constraints: fine-grained algorithms where the removal of a value for a variable will be propagated to the corresponding values for other variables, and coarse-grained algorithms where the removal of a value will be propagated to the related variables. One big advantage of coarse-grained algorithms, like AC-3, over fine-grained algorithms, like AC-4, is the ease of integration when implementing an algorithm in a constraint solver. However, fine-grained algorithms usually have optimal worst case time complexity while coarse-grained algorithms do not. For example, AC-3 is an algorithm with non-optimal worst case complexity although it is simple, efficient in practice, and widely used. In this paper we propose a coarse-grained algorithm, AC2001/3.1, that is worst case optimal and preserves as much as possible the ease of its integration into a solver (no heavy data structure to be maintained during search). Experimental results show that AC2001/3.1 is competitive with the best fine-grained algorithms such as AC-6. The idea behind the new algorithm can immediately be applied to obtain a path consistency algorithm that has the best-known time and space complexity. The same idea is then extended to non-binary constraints. © 2005 Elsevier B.V. All rights reserved.
Sat, 01 Jan 2005 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/392942005-01-01T00:00:00Z
- Improving host-based IDS with argument abstraction to prevent mimicry attackshttps://scholarbank.nus.edu.sg/handle/10635/43160Title: Improving host-based IDS with argument abstraction to prevent mimicry attacks
Authors: Sufatrio; Yap, R.H.C.
Abstract: A popular class of host-based Intrusion Detection Systems (IDS) are those based on comparing thesystem call trace of a process against a set of fc-grams. However, the detection mechanism in such IDS can be evaded by cloaking an attack as a mimicry attack. In this paper, we give an algorithm that transforms a detectable attack into a mimicry attack. We demonstrate on a number of examples that using this algorithm, mimicry attacks can be easily constructed on self-based IDS with a set of k-grams and also a more precise graph profile representation. We enhance the IDS by making use of the system call arguments and process credentials. To avoid increasing the false positives, a supplied specification is used to abstract the system call arguments and process credentials. The specification takes into account what objects in the system that can be sensitive to potential attacks, and highlights the occurrence of "dangerous" operations. With this simple extension, we show that the robustness of the IDS is increased. Our preliminary experiments show that on our example programs and attacks, it was no longer possible to construct mimicry attacks. We also demonstrate that the enhanced IDS provides resistance to a variety of common attack strategies. © Springer-Verlag Berlin Heidelberg 2006.
Sun, 01 Jan 2006 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/431602006-01-01T00:00:00Z
- Small world networks as (Semi)-structured overlay networkshttps://scholarbank.nus.edu.sg/handle/10635/40701Title: Small world networks as (Semi)-structured overlay networks
Authors: Halim, F.; Wu, Y.; Yap, R.H.C.
Abstract: Recent research has shown that Small World Network (SWN) is navigable. In this position paper, we propose that SWN, for example those which are social networks, have nice properties which make them attractive as overlay networks. Such networks occupy a space between structured and unstructured overlay networks. Our thesis is that SWN may be attractive enough to be a replacement for traditional structured overlay networks which are usually based on Chord-style Distributed Hash Tables. Preliminary experiment results show that without node failure, the performance ofgreedy routing in SWN works very well and with additional links in SWN the robustness in routing can be improved as well as the resilience against node/link failure. © 2008 IEEE.
Tue, 01 Jan 2008 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/407012008-01-01T00:00:00Z
- Approximate satisfiability countinghttps://scholarbank.nus.edu.sg/handle/10635/41620Title: Approximate satisfiability counting
Authors: Andrei, Ş.; Yap, R.H.C.; Manolache, G.; Felea, V.
Abstract: The problem of counting satisfiability, i.e. count the number of satisfying assignments for a SAT problem, is used successfully in a number of problems. For example, it can provide heuristics for guiding planning and search, where an estimation of the probability for a given search would help lead to a goal. Counting satisfiability is a valuable approach for problems like constraint satisfaction, knowledge compilation, probabilistic reasoning and computing the permanent of a Boolean matrix. The difficulty with counting satisfiability is that it is as hard as NP-complete problems, but probably much harder. This means that solvers to count the exact number of solutions may need a large amount on time on large propositional formulas. In this paper, we provide a fast alternative by approximating the number of instances. Our technique is based on successive variable and clause elimination. Experimental results demonstrate that our technique is promising. © 2008 IEEE.
Mon, 01 Jan 2007 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/416202007-01-01T00:00:00Z
- Visualization for analyzing trajectory-based metaheuristic search algorithmshttps://scholarbank.nus.edu.sg/handle/10635/77942Title: Visualization for analyzing trajectory-based metaheuristic search algorithms
Authors: Halim, S.; Yap, R.H.C.; Lau, H.C.
Sun, 01 Jan 2006 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/779422006-01-01T00:00:00Z
- Maintaining generalized arc consistency on Ad-hoc n-ary boolean constraintshttps://scholarbank.nus.edu.sg/handle/10635/77881Title: Maintaining generalized arc consistency on Ad-hoc n-ary boolean constraints
Authors: Cheng, K.C.K.; Yap, R.H.C.
Abstract: Binary decision diagrams (BDDs) can compactly rep- resent ad-hoc n-ary Boolean constraints. However, there is no gen- eralized arc consistency (GAC) algorithm which exploit BDDs. For example, the global case constraint by SICStus Prolog for ad-hoc constraints is designed for non-Boolean domains. In this paper, we introduce a new GAC algorithm, bddc, for BDD constraints. Our empirical results demonstrate the advantages of a new BDD-based global constraint-bddc is more efficient both in terms of mem- ory and time than the case constraint when dealing with ad-hoc Boolean constraints. This becomes important as the size of the ad- hoc constraints becomes large. © 2006 The authors.
Sun, 01 Jan 2006 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/778812006-01-01T00:00:00Z
- Constrained decision diagramshttps://scholarbank.nus.edu.sg/handle/10635/40534Title: Constrained decision diagrams
Authors: Cheng, K.C.K.; Yap, R.H.C.
Abstract: A general n-ary constraint is usually represented explicitly as a set of its solution tuples, which may need exponential space. In this paper, we introduce a new representation for general n-ary constraints called Constrained Decision Diagram (CDD). CDD generalizes BDD-style representations and the main feature is that it combines constraint reasoning/consistency techniques with a compact data structure. We present an application of CDD for recording all solutions of a conjunction of constraints. Instead of an explicit representation, we can implicitly encode the solutions by means of constraint propagation. Our experiments confirm the scalability and demonstrate that CDDs can drastically reduce the space needed over explicit and ZBDD representations. Copyright © 2005, American Association for Artificial Intelligence (www.aaai.org). All rights reserved.
Sat, 01 Jan 2005 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/405342005-01-01T00:00:00Z
- The problem of usable binary authenticationhttps://scholarbank.nus.edu.sg/handle/10635/43169Title: The problem of usable binary authentication
Authors: Wu, Y.; Yap, R.H.C.
Abstract: Attacks by malware usually work by getting a binary to be executed. Sometimes users are unaware that such binaries are being executed. The end result is that attackers can either compromise a system or get it to fail. One defence against such attacks is to ensure integrity of files. A more comprehensive mechanism is binary authentication (code signing is also a form of binary authentication) which tries to ensure that any binaries loaded by the operating system and software applications are first authenticated, i.e. the content of the binary is known and is trusted. To have full protection using binary authentication, it makes sense to have a default deny policy where binaries which do not pass authentication are prevented from executing. However, if an operating system employs mandatory binary authentication for protection purposes, the end result may either be not user friendly or not very usable. In this paper, we discuss the issues and difficulties of making binary authentication usable on the Windows operating system. © 2010 IEEE.
Fri, 01 Jan 2010 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/431692010-01-01T00:00:00Z
- Trusted principal-hosted certificate revocationhttps://scholarbank.nus.edu.sg/handle/10635/43151Title: Trusted principal-hosted certificate revocation
Authors: Sufatrio; Yap, R.H.C.
Abstract: Public Key Infrastructure is a key infrastructure for secure and trusted communication on the Internet. This paper revisits the problem of providing timely certificate revocation focusing on the needs of mobile devices. We survey existing schemes then present a new approach where the principal's server functions as the directory for its own revocation information. We evaluate the properties and trust requirements in this approach, and propose two new schemes, CREV-I and CREV-II, which meet the security requirements and performance goals. Evaluation of CREV shows it is more lightweight on the verifier and more scalable at the CA and the principals while providing near real-time revocation. © 2011 International Federation for Information Processing.
Sat, 01 Jan 2011 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/431512011-01-01T00:00:00Z
- Implementing CSAT local search on FPGAshttps://scholarbank.nus.edu.sg/handle/10635/40787Title: Implementing CSAT local search on FPGAs
Authors: Henz, M.; Tan, E.; Yap, R.H.C.
Abstract: Stochastic local search methods such as GSAT, WalkSAT and their variants have been used successfully at solving propositional satisfiability problems (SAT). The key operation in these local search algorithms is the speed of variable flipping. We present a parallel FPGA designs for CSAT capable of one flip per clock cycle which is achieved by exploiting maximal parallelism and "multi-try" pipelining. Experimental results show that a speedup of two orders of magnitude over software implementations can be achieved. © Springer-Verlag Berlin Heidelberg 2002.
Tue, 01 Jan 2002 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/407872002-01-01T00:00:00Z
- Generalized committed choicehttps://scholarbank.nus.edu.sg/handle/10635/40845Title: Generalized committed choice
Authors: Jaffar, J.; Yap, R.H.C.; Zhu, K.Q.
Abstract: We present a generalized committed choice construct for concurrent programs that interact with a shared store. The generalized committed choice (GCC) allows multiple computations from different alternatives to occur concurrently and later commit to one of them. GCC generalizes the traditional committed choice in Dijkstra's Guarded Command Language to handle don't know non-determinism and also allows for speculative computation. The main contribution of the paper is to introduce the GCC programming construct and the associated semantics framework for formalizing GCC. We give some experimental results which show that the power of GCC can be made practical. © Springer-Verlag Berlin Heidelberg 2007.
Mon, 01 Jan 2007 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/408452007-01-01T00:00:00Z
- Viz: A visual analysis suite for explaining local search behaviorhttps://scholarbank.nus.edu.sg/handle/10635/43239Title: Viz: A visual analysis suite for explaining local search behavior
Authors: Halim, S.; Yap, R.H.C.; Lau, H.C.
Abstract: NP-hard combinatorial optimization problems are common in real life. Due to their intractability, local search algorithms are often used to solve such problems. Since these algorithms are heuristic-based, it is hard to understand how to improve or tune them. We propose an interactive visualization tool, Viz, meant for understanding the behavior of local search. Viz uses animation of abstract search trajectories with other visualizations which are also animated in a VCR-like fashion to graphically playback the algorithm behavior. It combines generic visualizations applicable on arbitrary algorithms with algorithm and problem specific visualizations. We use a variety of techniques such as alpha blending to reduce visual clutter and to smooth animation, highlights and shading, automatically generated index points for playback, and visual comparison of two algorithms. The use of multiple viewpoints can be an effective way of understanding search behavior and highlight algorithm behavior which might otherwise be hidden. Copyright 2006 ACM.
Tue, 01 Jan 2008 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/432392008-01-01T00:00:00Z
- Viz: A visual analysis suite for explaining local search behaviorhttps://scholarbank.nus.edu.sg/handle/10635/43237Title: Viz: A visual analysis suite for explaining local search behavior
Authors: Halim, S.; Yap, R.H.C.; Lau, H.C.
Abstract: NP-hard combinatorial optimization problems are common in real life. Due to their intractability, local search algorithms are often used to solve such problems. Since these algorithms are heuristic-based, it is hard to understand how to improve or tune them. We propose an interactive visualization tool, Viz, meant for understanding the behavior of local search. Viz uses animation of abstract search trajectories with other visualizations which are also animated in a VCR-like fashion to graphically playback the algorithm behavior. It combines generic visualizations applicable on arbitrary algorithms with algorithm and problem specific visualizations. We use a variety of techniques such as alpha blending to reduce visual clutter and to smooth animation, highlights and shading, automatically generated index points for playback, and visual comparison of two algorithms. The use of multiple viewpoints can be an effective way of understanding search behavior and highlight algorithm behavior which might otherwise be hidden. Copyright 2006 ACM.
Sun, 01 Jan 2006 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/432372006-01-01T00:00:00Z
- A lightweight binary authentication system for windowshttps://scholarbank.nus.edu.sg/handle/10635/43234Title: A lightweight binary authentication system for windows
Authors: Halim, F.; Ramnath, R.; Sufatrio, R.R.; Wu, Y.; Yap, R.H.
Abstract: The problem of malware is greatly reduced if we can ensure that only software from trusted providers is executed. In this paper, we have built a prototype system on Windows which performs authentication of all binaries in Windows to ensure that only trusted software is executed and from the correct path. Binaries on Windows are made more complex because there are many kinds of binaries besides executables, e.g. DLLs, drivers, ActiveX controls, etc.We combine this with a simple software ID scheme for software management and vulnerability assessment which leverages on trusted infrastructure such as DNS and Certificate Authorities. Our prototype is lightweight and does not need to rely on PKI infrastructure; it does however take advantage of binaries with existing digital signatures. We provide a detailed security analysis of our authentication scheme. We demonstrate that our prototype has low overhead, around 2%, even when all binary code is authenticated. © 2008 International Federation for Information Processing.
Tue, 01 Jan 2008 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/432342008-01-01T00:00:00Z
- Visualizing Windows system traceshttps://scholarbank.nus.edu.sg/handle/10635/43235Title: Visualizing Windows system traces
Authors: Wu, Y.; Yap, R.H.C.; Halim, F.
Abstract: Operating system traces contain the detailed behavior of the persistent actions of an application; interactions between multiple applications; and the functioning of the system as a whole. The challenge is that such traces are large and consequently hard to understand and analyze. We present lviz, a novel visualization tool, which meets these challenges. We focus on Windows system traces though our visualization is general. Our visualization is exible and can be customized to highlight different aspects of the behavior program(s) and the overall operating system. Copyright 2010 ACM.
Fri, 01 Jan 2010 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/432352010-01-01T00:00:00Z
- Routing in the watts and strogatz small world networks revisitedhttps://scholarbank.nus.edu.sg/handle/10635/43236Title: Routing in the watts and strogatz small world networks revisited
Authors: Halim, F.; Wu, Y.; Yap, R.H.C.
Sat, 01 Jan 2011 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/432362011-01-01T00:00:00Z
- Partial social network disclosure and crawlershttps://scholarbank.nus.edu.sg/handle/10635/40702Title: Partial social network disclosure and crawlers
Authors: Effendy, S.; Halim, F.; Yap, R.H.C.
Abstract: The popularity and size of online social networks means the social graph contains valuable data about relationships. Such graph data may be sensitive. Thus, there is a need to protect the data from privacy leaks. On the other hand, public information and crawl ability are needed to support the basic utility and services on top of the social network. We propose policies where the owner of the social network can tradeoff between these two conflicting goals. We experiment with real world social network graphs and show that the owner of the graph can employ policies which can meet particular tradeoffs under different crawlers. Furthermore, the policies are efficient and scalable for the owner of the social network. © 2011 IEEE.
Sat, 01 Jan 2011 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/407022011-01-01T00:00:00Z
- Wiki credibility enhancementhttps://scholarbank.nus.edu.sg/handle/10635/40705Title: Wiki credibility enhancement
Authors: Halim, F.; Yongzheng, W.; Yap, R.
Abstract: Wikipedia has been very successful as an open encyclopedia which is editable by anybody. However, the anonymous nature of Wikipedia means that readers may have less trust since there is no way of verifying the credibility of the authors or contributors. We propose to automatically transfer external information about the authors from outside Wikipedia to Wikipedia pages. This additional information is meant to enhance the credibility of the content. For example, it could be the education level, professional expertise or affiliation of the author. We do this while maintaining anonymity. In this paper, we present the design and architecture of such system together with a prototype. Copyright 2009 ACM.
Thu, 01 Jan 2009 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/407052009-01-01T00:00:00Z
- Engineering stochastic local search for the low autocorrelation binary sequence problemhttps://scholarbank.nus.edu.sg/handle/10635/40704Title: Engineering stochastic local search for the low autocorrelation binary sequence problem
Authors: Halim, S.; Yap, R.H.C.; Halim, F.
Abstract: This paper engineers a new state-of-the-art Stochastic Local Search (SLS) for the Low Autocorrelation Binary Sequence (LABS) problem. The new SLS solver is obtained with white-box visualization to get insights on how an SLS can be effective for LABS; implementation improvements; and black-box parameter tuning. © 2008 Springer-Verlag Berlin Heidelberg.
Tue, 01 Jan 2008 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/407042008-01-01T00:00:00Z
- Fast and effective histogram constructionhttps://scholarbank.nus.edu.sg/handle/10635/40707Title: Fast and effective histogram construction
Authors: Halim, F.; Karras, P.; Yap, R.H.C.
Abstract: Histogram construction or sequence segmentation is a basic task with applications in database systems, information retrieval, and knowledge management. Its aim is to approximate a sequence by line segments. Unfortunately, the quadratic algorithm that derives an optimal histogram for Euclidean error lacks the desired scalability. Therefore, sophisticated approximation algorithms have been recently proposed, while several simple heuristics are used in practice. Still, these solutions fail to resolve the efficiency-quality tradeoff in a satisfactory manner. In this paper we take a fresh view on the problem. We propose conceptually clear and scalable algorithms that efficiently derive high-quality histograms. We experimentally demonstrate that existing approximation schemes fail to deliver the desired efficiency and conventional heuristics do not fare well on the side of quality. On the other hand, our schemes match or exceed the quality of the former and the efficiency of the latter. Copyright 2009 ACM.
Thu, 01 Jan 2009 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/407072009-01-01T00:00:00Z
- Local search in histogram constructionhttps://scholarbank.nus.edu.sg/handle/10635/40709Title: Local search in histogram construction
Authors: Halim, F.; Karras, P.; Yap, R.H.C.
Abstract: The problem of dividing a sequence of values into segments occurs in database systems, information retrieval, and knowl edge management. The challenge is to select a finite number of boundaries for the segments so as to optimize an objective error function defined over those segments. Although this optimization problem can be solved in polynomial time, the algorithm which achieves the minimum error does not scale well, hence it is not practical for applications with massive data sets. There is considerable research with numerous approximation and heuristic algorithms. Still, none of those approaches has resolved the quality-efficiency tradeoff in a satisfactory manner. In (Halim, Karras, and Yap 2009), we obtain near linear time algorithms which achieve both the desired scalability and near-optimal quality, thus dominating earlier approaches. In this paper, we show how two ideas from artificial intelligence, an efficient local search and recombination of multiple solutions reminiscent of genetic algorithms, are combined in a novel way to obtain state of the art histogram construction algorithms. Copyright © 2010, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved.
Fri, 01 Jan 2010 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/407092010-01-01T00:00:00Z
- Designing and tuning SLS through animation and graphics: An extended walk-throughhttps://scholarbank.nus.edu.sg/handle/10635/40710Title: Designing and tuning SLS through animation and graphics: An extended walk-through
Authors: Halim, S.; Yap, R.H.C.
Abstract: Stochastic Local Search (SLS) is quite effective for a variety of Combinatorial (Optimization) Problems. However, the performance of SLS depends on several factors and getting it right is not trivial. In practice, SLS may have to be carefully designed and tuned to give good results. Often this is done in an ad-hoc fashion. One approach to this issue is to use a tuning algorithm for finding good parameter settings to a black-box SLS algorithm. Another approach is white-box which takes advantage of the human in the process. In this paper, we show how visualization using a generic visual tool can be effective for a white-box approach to get the right SLS behavior on the fitness landscape of the problem instances at hand. We illustrate this by means of an extended walk-through on the Quadratic Assignment Problem. At the same time, we present the human-centric tool which has been developed. © Springer-Verlag Berlin Heidelberg 2007.
Mon, 01 Jan 2007 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/407102007-01-01T00:00:00Z
- Automatic information extraction from web pageshttps://scholarbank.nus.edu.sg/handle/10635/40555Title: Automatic information extraction from web pages
Authors: Rahardjo, B.; Yap, R.H.C.
Abstract: Many web pages have implicit structure. In this paper, we show the feasibility of automatically extracting data from web pages by using approximate matching techniques. This can be applied to generate automatic wrappers or to notify/display web page differences, web page change monitoring, etc.
Mon, 01 Jan 2001 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/405552001-01-01T00:00:00Z
- Indexing for dynamic abstract regionshttps://scholarbank.nus.edu.sg/handle/10635/40573Title: Indexing for dynamic abstract regions
Authors: Jaffar, J.; Yap, R.H.C.; Zhu, K.Q.
Abstract: We propose a new main memory index structure for abstract regions (objects) which may heavily overlap, the RC-tree. These objects are "dynamic" and may have short life spans. The novelty is that rather than representing an object by its minimum bounding rectangle (MBR), possibly with pre-processed segmentation into many small MBRs, we use the actual shape of the object to maintain the index. This saves significant space for objects with large spatial extents since pre-segmentation is not needed. We show that the query performance of RC-tree is much better than many indexing schemes on synthetic overlapping data sets. The performance is also competitive on real-life GIS non-overlapping data sets. © 2006 IEEE.
Sun, 01 Jan 2006 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/405732006-01-01T00:00:00Z
- Robust controllability of temporal constraint networks under uncertaintyhttps://scholarbank.nus.edu.sg/handle/10635/40564Title: Robust controllability of temporal constraint networks under uncertainty
Authors: Lau, H.C.; Li, J.; Yap, R.H.C.
Abstract: Temporal constraint networks are embedded in many planning and scheduling problems. In dynamic problems, a fundamental challenge is to decide whether such a network can be executed as uncertainty is revealed over time. Very little work in this domain has been done in the probabilistic context. In this paper, we propose a Temporal Constraint Network (TCN) model where durations of uncertain activities are represented by random variables. We wish to know whether such a network is robust controllable, i.e. can be executed dynamically within a given failure probability, and if so, how one might find a feasible schedule as the uncertainty variables are revealed dynamically. We present a computationally tractable and efficient approach to solve this problem. Experimentally, we study how the failure probability is affected by various network properties of the underlying TCN, and the relationship of failure rates between robust and weak controllability. © 2006 IEEE.
Sun, 01 Jan 2006 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/405642006-01-01T00:00:00Z
- An integrated white+black box approach for designing and tuning stochastic local searchhttps://scholarbank.nus.edu.sg/handle/10635/40637Title: An integrated white+black box approach for designing and tuning stochastic local search
Authors: Halim, S.; Yap, R.H.C.; Lau, H.C.
Abstract: Stochastic Local Search (SLS) is a simple and effective paradigm for attacking a variety of Combinatorial (Optimization) Problems (COP). However, it is often non-trivial to get good results from an SLS; the designer of an SLS needs to undertake a laborious and ad-hoc algorithm tuning and re-design process for a particular COP. There are two general approaches, Black-box approach treats the SLS as a black-box in tuning the SLS parameters. White-box approach takes advantage of humans to observe the SLS in the tuning and SLS re-design. In this paper, we develop an integrated white+black box approach with extensive use of visualization (white-box) and factorial design (black-box) for tuning, and more importantly, for designing arbitrary SLS algorithms. Our integrated approach combines the strengths of white-box and black-box approaches and produces better results than either alone. We demonstrate an effective tool using the integrated white+black box approach to design and tune variants of Robust Tabu Search (Ro-TS) for Quadratic Assignment Problem (QAP). © Springer-Verlag Berlin Heidelberg 2007.
Mon, 01 Jan 2007 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/406372007-01-01T00:00:00Z
- Codejail: Application-transparent isolation of libraries with tight program interactionshttps://scholarbank.nus.edu.sg/handle/10635/40142Title: Codejail: Application-transparent isolation of libraries with tight program interactions
Authors: Wu, Y.; Sathyanarayan, S.; Yap, R.H.C.; Liang, Z.
Abstract: Dynamically linked libraries are commonly used in software programs to facilitate code reuse. Once a library is linked into a software program, a bug in the library can lead to compromise of the whole program. Moreover, the library may also contain malicious code. Existing solutions for software component isolation assume simple interactions between a library and the main program, otherwise, they require significant modification of the main program and the library. In this paper, we propose a novel solution, Codejail, which supports a partial isolation of libraries that have tight memory interactions with the main program. Codejail requires no modification to the main program or the library. We demonstrate using a Linux prototype that Codejail can work easily with real-world programs and libraries. The performance is good for a portable implementation with costs commensurate with the degree of tight interaction. © 2012 Springer-Verlag.
Sun, 01 Jan 2012 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/401422012-01-01T00:00:00Z
- Constraint Programming 2000: A Position Paperhttps://scholarbank.nus.edu.sg/handle/10635/99226Title: Constraint Programming 2000: A Position Paper
Authors: Jaffar, J.; Yap, R.H.C.
Abstract: We put forward that required enhancements to constraint programming technology include concurrency, more sophisticated control mechanisms, and new features for expressing preferences.
Wed, 01 Jan 1997 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/992261997-01-01T00:00:00Z
- Meta-programming in CLP(ℛ)https://scholarbank.nus.edu.sg/handle/10635/99334Title: Meta-programming in CLP(ℛ)
Authors: Heintze, N.; Michaylov, S.; Stuckey, P.J.; Yap, R.H.C.
Abstract: A widely used property of Prolog is that it is possible to write Prolog programs to construct and manipulate other Prolog programs in a very general manner. Unfortunately, this property is not carried over to richer languages such as CLP(ℛ) - the manipulation of CLP(ℛ) programs in CLP(ℛ) is quite limited. The reason is that the equality of terms in CLP(ℛ) is not based on their syntactic structure. We propose an extended language, CLP(ℛ + script M sign;), in which programs may be represented and structurally manipulated. Importantly, CLP(ℛ + script M sign;) is not just a meta-language for CLP(ℛ), but it can also be used as its own meta-language. We present a decision algorithm for ℛ + script M sign; constraints, discuss implementation issues, and describe the implementation of a subclass of ℛ + script M sign; constraints. Finally, by building on the extended language, we present an integrated set of system predicates and a methodology for practical meta-programming. © Elsevier Science Inc., 1997.
Mon, 01 Dec 1997 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/993341997-12-01T00:00:00Z
- Consistency and set intersectionhttps://scholarbank.nus.edu.sg/handle/10635/40387Title: Consistency and set intersection
Authors: Zhang, Y.; Yap, R.H.C.
Abstract: A new framework to study consistency in terms of general properties of set intersection was presented. The significance of such set intersection results is that they can be lifted directly to a constraint network setting to obtain consistency results. A proof schema to lift these results was also given.
Tue, 01 Jan 2002 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/403872002-01-01T00:00:00Z
- Establishing software integrity trust: A survey and lightweight authentication system for windowshttps://scholarbank.nus.edu.sg/handle/10635/78456Title: Establishing software integrity trust: A survey and lightweight authentication system for windows
Authors: Wu, Y.; Sufatrio; Yap, R.H.C.; Ramnath, R.; Halim, F.
Abstract: Malware causes damage by stealing confidential data or making other software unusable. Ensuring software trustworthiness is difficult because malware may disguise itself to appear benign or trusted. This chapter explores the problem of making software more trustworthy through the use of binary integrity mechanisms. The authors review the problem of devising an effective binary integrity protection, and discuss how it complements other operating system security measures. They analyze design factors for binary integrity and compare existing systems. The authors then present a prototype which exemplifies a mandatory binary integrity mechanism and its integration within an operating system. Their system, BinAuth, demonstrates a practical, lightweight in-kernel binary authentication system for Microsoft Windows. A system like BinAuth shows that mandatory authentication is practical on complex commodity operating system like Windows. To deal with various constraints in the user's environments, BinAuth uses a flexible scheme which does not mandate public key infrastructure (PKI) although it can take advantage of it. The authors also combine the authentication with a simple software-ID scheme which is useful for software management and vulnerability assessment. © 2010, IGI Global.
Fri, 01 Jan 2010 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/784562010-01-01T00:00:00Z
- Towards a general framework for secure MapReduce computation on hybrid cloudshttps://scholarbank.nus.edu.sg/handle/10635/78398Title: Towards a general framework for secure MapReduce computation on hybrid clouds
Authors: Zhang, C.; Chang, E.-C.; Yap, R.H.C.
Abstract: The idea of a hybrid cloud is to combine a private cloud (e.g., an organization's in-house private datacenter) together with a public cloud (e.g., Amazon EC2). Hybrid cloud computing offers increased scalability and cost-effectiveness: the private cloud can be used for typical workloads, but when additional resources are needed during peak computations, the public cloud is harnessed. This hybrid cloud architecture has already gained adoption [1] and is still undergoing rapid development [4].
Tue, 01 Jan 2013 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/783982013-01-01T00:00:00Z
- Making AC-3 an optimal algorithmhttps://scholarbank.nus.edu.sg/handle/10635/78218Title: Making AC-3 an optimal algorithm
Authors: Zhang, Y.; Yap, R.H.C.
Abstract: The AC-3 algorithm is a basic and widely used arc consistency enforcing algorithm in Constraint Satisfaction Problems (CSP). Its strength lies in that it is simple, empirically efficient and extensible. However its worst case time complexity was not considered optimal since the first complexity result for AC-3 [Mackworth and Freuder, 1985] with the bound O(ed3), where e is the number of constraints and d the size of the largest domain. In this paper, we show suprisingly that AC-3 achieves the optimal worst case time complexity with O(ed2). The result is applied to obtain a path consistency algorithm which has the same time and space complexity as the best known theoretical results. Our experimental results show that the new approach to AC-3 is comparable to the traditional AC-3 implementation for simpler problems where AC-3 is more efficient than other algorithms and significantly faster on hard instances.
Mon, 01 Jan 2001 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/782182001-01-01T00:00:00Z
- JNICodejail - Native code isolation for Java programshttps://scholarbank.nus.edu.sg/handle/10635/78207Title: JNICodejail - Native code isolation for Java programs
Authors: Hassanshahi, B.; Yap, R.H.C.
Abstract: The Java Native Interface (JNI) allows Java programmers to inter-operate with code written in other languages like C and C++. One reason to use JNI is to get higher performance. Other reasons are to access low-level implementation features not available in pure Java and facilitate the reuse of existing code and libraries. However, the drawback is that native code can be used to compromise the security of the rest of Java. In this paper, we propose JNICodejail, which sandboxes the native code used in JNI. JNICodejail ensures that the native code is unable to affect the rest of Java (except what is allowed through JNI) and is confined only with the appropriate system privileges. However, native code is allowed to read memory outside its sandbox, thus, it is possible to share data which is read-only with the sandbox for improved efficiency. A recent alternative for sandboxing JNI native code is Arabica. We demonstrate that our JNICodejail prototype can have reasonable performance with respect to both normal un-sandboxed JNI execution and sandboxing with Arabica.
Tue, 01 Jan 2013 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/782072013-01-01T00:00:00Z
- Optimizing STR algorithms with tuple compressionhttps://scholarbank.nus.edu.sg/handle/10635/78274Title: Optimizing STR algorithms with tuple compression
Authors: Xia, W.; Yap, R.H.C.
Abstract: Table constraints define an arbitrary constraint explicitly as a set of solutions (tuples) or non-solutions. Thus, space is proportional to number of tuples. Simple Tabular Reduction (STR), which dynamically reduces the table size by maintaining a table of only the valid tuples, has been shown to be efficient for enforcing Generalized Arc Consistency. The Cartesian product representation is another way of having a smaller table by compression. We investigate whether STR and the Cartesian product representation can work hand in hand. Our experiments show the compression-based STR can be faster once the tables compress well. Thus, the benefits of the STR2 and STR3 algorithms respectively are retained while consuming less space. © 2013 Springer-Verlag.
Tue, 01 Jan 2013 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/782742013-01-01T00:00:00Z
- Fast algorithm for scheduling instructions with deadline constraints on RISC machineshttps://scholarbank.nus.edu.sg/handle/10635/40999Title: Fast algorithm for scheduling instructions with deadline constraints on RISC machines
Authors: Wu, Hui; Jaffar, Joxan; Yap, Roland
Abstract: We present a fast algorithm for scheduling UET(Unit Execution Time) instructions with deadline constraints in a basic block on RISC machines with multiple processors. Unlike Palem and Simon's algorithm, our algorithm allows latency of lij = -1 which denotes that instruction vj cannot be started before vi. The time complexity of our algorithms is O(ne + nd), where n is the number of instructions, e is the number of edges in the precedence graph and d is the maximum latency. Our algorithm is guaranteed to compute a feasible schedule whenever one exists in the following special cases: 1) Arbitrary precedence constraints, latencies in {0, 1} and one processor. In this special case, our algorithm improves the existing fastest algorithm from O(ne + e′ log n) to O(min{ne, n2.376}), where e′ is the number of edges in the transitively closed precedence graph. 2) Arbitrary precedence constraints, latencies in {-1, 0} and two processors. In the special case where all latencies are 0, our algorithm degenerates to Garey and Johnson's two processor algorithm. 3) Special precedence constraints in the form of monotone interval graph, arbitrary latencies in {-1, 0, 1, ..., d} and multiple processors. 4) Special precedence constraints in the form of in-forest, equal latencies and multiple processors. In the above special cases, if no feasible schedule exists, our algorithm will compute a schedule with minimum lateness. Moreover, by setting all deadlines to a sufficiently large integer, our algorithm will compute a schedule with minimum length in all the above special cases and the special case of out-forest, equal latencies and multiple processors.
Sat, 01 Jan 2000 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/409992000-01-01T00:00:00Z