Computer Science Graduate Seminar @ BGU

Abstract:
The ease of seeing conceals many complexities. A fundamental one is the problem of fragmentation – we are able to recognize objects although they are optically incomplete, e.g., due to occlusions. To overcome this difficulty, biological and artificial visual systems use a mechanism for contour completion, which has been studied by the many disciplines of vision science, mostly in an intra-disciplinary fashion. Recent computational, neurophysiological, and psychophysical studies suggest that completed contours emerge from activation patterns of orientation selective cells in the primary visual cortex, or V1. In this work we suggest modeling these patterns as 3D curves in the mathematical continuous space R^2 × S^1, a.k.a. the unit tangent bundle associated with the image plane R^2, that abstracts V1. Then, we propose that the completed shape may follow physical/biological principles which are conveniently abstracted and analyzed in this space. We implement our theories by numerical algorithms to show ample experimental results of visually completed curves in natural and synthetic scenes.

Abstract:
A popular approach to deal with the "curse of dimensionality" in relation with high-dimensional data analysis is to assume that points in these datasets lie on a low-dimensional manifold immersed in a high-dimensional ambient space. Kernel methods operate on this assumption and introduce the notion of local affinities between data points via the construction of a suitable kernel. Spectral analysis of this kernel provides a global, preferably low-dimensional, coordinate system that preserves the qualities of the manifold. In this presentation, the scalar relations used in this framework will be extended to matrix relations, which can encompass multidimensional similarities between local neighborhoods of points on the manifold. We utilize the diffusion maps methodology together with linear-projection operators between tangent spaces of the manifold to construct a super-kernel that represents these relations. The properties of the presented super- kernels are explored and their spectral decompositions are utilized to embed the patches of the manifold into a tensor space in which the relations between them are revealed. Two applications of the patch- to-tensor embedding framework for data clustering and classification will be presented.

Abstract:
Two key synchronization paradigms for the construction of scalable concurrent data-structures are software combining and elimination. Elimination-based concurrent data-structures allow operations with reverse semantics (such as push and pop stack operations) to "collide" and exchange values without having to access a central location. Software combining, on the other hand, is effective when colliding operations have identical semantics: when a pair of threads performing operations with identical semantics collide, the task of performing the combined set of operations is delegated to one of the threads and the other thread waits for its operation(s) to be performed. Applying this mechanism iteratively can reduce memory contention and increase throughput.

We present DECS, a novel Dynamic Elimination-Combining Stack algorithm, that scales well for all workload types. While maintaining the simplicity and low-overhead of an elimination-based stack, DECS manages to benefit from collisions of both identical- and reverse-semantics operations. Our empirical evaluation shows that DECS scales significantly better than both blocking and non-blocking best prior stack algorithms.

This is joint work with Gal Bar-Nissan and Danny Hendler.

Abstract:
FINCH (Fertile DarwINian ByteCode Harvester), is a methodology for evolving Java bytecode, enabling the evolution of extant, unrestricted Java programs, or programs in other languages that compile to Java bytecode. FINCH is based upon the notion of compatible crossover, which produces correct programs by performing operand stack-, local variables-, and control flow-based compatibility checks on source and destination bytecode sections--unlike earlier work that uses restricted subsets of the Java bytecode instruction set as a representation language for individuals in genetic programming. We demonstrate FINCH's unqualified success at solving a host of problems, including simple and complex regression, trail navigation, image classification, array sum, tic-tac-toe, and evolution of game heuristics. FINCH exploits the richness of the Java Virtual Machine architecture and type system, ultimately evolving human-readable solutions in the form of Java programs. The ability to evolve Java programs will hopefully lead to a valuable new tool in the software engineer's toolkit.

Abstract:
Detection and containment of unknown malware are challenging tasks. Typically the detection is performed by experts who use anomaly detection systems or Honeypots-based systems. Such a detection process is very slow and it is not suited for detection of rapidly propagating threats such as worms. In this research we propose to automate the detection process by introducing an innovative distributed framework for detection and containment of new malware. The framework consists of distributed agents that are installed in several client computers and a Centralized Decision Maker module (CDM) that interacts with the agents. The new detection process is performed in two phases. In the first phase agents detect potential malware on local machines and send their detection results to the CDM. In the second phase, the CDM builds a propagation graph for every potential malware. These propagation graphs are compared to known malware propagation characteristics in order to determine whether the potential malware is indeed a malware. All the agents are notified of a final decision in order to start the containment process.
Another contribution of this study is a method for detecting new malicious executables locally. It is based on monitoring run-time system calls and comprises the following steps: (a) in an offline training phase, finding a set of (not necessary consecutive) system call sequences that are characteristic only to malicious files, when such malicious files are executed, and storing said sequences in a database; (b) in a real time detection phase, for each running executable, continuously monitoring its issued system calls and comparing them with the stored sequences of system calls within the database to determine whether there exists a match between a portion of the sequence of the run-time system calls and one or more of the database sequences, and when such a match is found, declaring said executable as malicious. In addition to the collaborative detection, the method can be used for independent (local) malware detection, replacing (or in addition to) traditional antivirus software.