|
Sidan är under uppdatering. Essay Project ProposalsThemes: Security, protocols and systems, programming languages, language technology, artificial intelligence, algorithms, computer graphics, simulation SecurityTitle: Fuzzing Theme: Security Subject: Fuzzing is a technique for software vulnerability testing. The idea is to provide applications with ranges of valid or invalid input and in this way try to cause the application to act in an unexpected or faulty manner. An efficient fuzzer will give good coverage at small cost, i.e. it will generate as many and as diverse faults as possible while using as few and as small tests as possible. The inputs may be randomly generated, or they may be guided by knowledge of the protocols and applications, and by heuristics, i.e. test generation strategies that are known to often give good results for the type of application under stress. Often, some form of grammar is used to generate the well-formed inputs and otherwise guide the test generation process. Examples of fuzzers suitable for this project:
CAVEAT: *Never* attempt to perform vulnerability or penetration testing without proper authorization! Possible essay projects:
References:
Title: Security Monitoring Theme: Security Subject: Security monitoring is a technique used to enforce security policies, for instance for access control. A very general and flexible approach to security monitoring uses automata to represent security policies. For instance, a security automaton with two states *unchecked* and *checked* can be used to define the policy that boarding of an aircraft should be allowed only after check in has been properly completed. In an ongoing EU project HATS (www.hats-project.org) we are exploring the use of security automata and automata inlining for multithreaded Java and a prototype inliner has been developed. A lot of open ends are left, however, which may be suitable for small student projects. Possible essay projects:
References:
Contact: Get in touch with Mads or PhD student Andreas Lundblad in the theory corridor if you are interested in this line of work. Supervisor: Mads Dam Title: Multilevel secure programming Theme: Security Subject: Many programs need to process data with different security requirements. A webshop, for instance, may need to process data on behalf of customers, payment receivers, and suppliers, with different requirements regarding confidentiality and integrity. In multilevel security data is assigned security levels in some security lattice, and a multilevel secure program must respect this lattice such that data e.g. at a high confidentility level cannot be read by agents at level "public". Several prototype languages such as FlowCAML and JIF have been developed over the recent years to support multilevel secure programming using type systems. A project in the area of multilevel secure programming might experiment with such a language to try it out on a concrete application, or it might document or compare some approaches to multilevel security in the literature. Possible essay projects:
References:
Contact: Seeral researchers in the theory group is currently active in this research area. Talk to a member of {Mads,Gurvan le Guernic,Musard Balliu} if you are interested in joining this work. Supervisor: Mads Dam Title: Proof of work Theme: Security Subject: One way to try to avoid DOS attacks,
brute force attacks or having someone use a mail server for mass email
(SPAM) is to use a proof of work
protocol. Essentially it involves the server not processing a client
request right away. Instead it sends a Study, present and implement a proof of work protocol. Explain assumptions and examine performance. References:
Supervisor: Mikael Goldmann Title: Secure multiparty computation Theme: Security Subject: In the design of secure cryptographic protocols, one important aspect is to define what it would mean for the protocol to be secure — without a definition of security, it is of course impossible to prove that a protocol is secure. The notion of an ideal functionality can be intuitively described by an example. Consider the fallowing sealed bid auction: There is a trusted person to whom all others can send a bid over a secure channel. Once the auction is over the winner is the one who handed in the highest bid, and that person pays the value of the second highest bid. The trusted person announces the winner and the value of the second highest bid amd the bidders do not learn anything else about the other bids. This would be our ideal functionality. Now, let us say that we want to remove the trusted person and instead use cryptography. We then want to prove that the cryptographic protocol behaves the same as the ideal functionality, i.e., that (for all practical purposes) the outcome is the same and the information leaked to the participants is the same. There are a number of frameworks available for implementing secure multiplarty computation. Use one or two to implement some simple examples. Document your examples and the properties of the framework(s). If you look at more than one, then do a comparison on e.g., usability and efficiency. References: Some frameworks Supervisor: Mikael Goldmann Title: Cognitive authentication schemes Theme: Security Subject: Cognitive authentication schemes are an alternative to password authentication. Passwords have the advantage of being simple to use as they only require you to remember a secret, but they are vulnerable to eavesdropping attacks such as key loggers that might be installed on a computer that you do not yourself control. As an alternative, there are schemes relying on the user to memorize a few images and the system then prompting the user with a set of images, some of which are among the one the user has memorized. A simplified description would be that the system presents the user with a matrix of images and the user responds by telling the system which rows contains pictures from the user's set. Repeating this a number of times decreases the likelihood that an attacker would guess the correct rows each time. After, say, 10 successful challenges the user is authenticated. Study such a scheme and either implement it and do usability tests or study and implement attacks on such a scheme. The report should describe the studied system, your tests and your findings. References:
Title: Net voting Theme: Security Subject: Most people agree that traditional ballot voting should be replaced by some form of net voting. The security issues have been deterrent so far, but now is the time to present an attractive solution. The goal of the project is to pinpoint the weak points and the fortes of different possibilities and to recommend the ultimate net voting system. Project highlights:
References:
Supervisor: Henrik Eriksson Protocols and SystemsTitle: System Virtualization Theme: Protocols and systems Subject: A hypervisor, or systems virtualizer, is a slim piece of systems software operating directly on top of processing hardware, allowing several guest systems to share a common physical processor. Virtualization is a key enabling technology for cloud computing, but it also is promising for embedded systems, for instance to provide memory separation between an (insecure) operating system implemented as one guest system and a set of security services as another guest system. In a research project currently running as a collaboration between SICS and the theory group at CSC we are developing a hypervisor for the ARM family of processors. In the context of this project it is possible to identify some interesting and challenging subjects that a suitable as essay projects. One topic might be to understand and document the design, and implement some benchmark tests together with the research student Oliver Schwarz at SICS currently responsible for the work. Interested students should get in touch with Mads. References
Supervisor: Mads Dam Title: Data Serialization, parsing, deparsing - Protobuf, Thrift, Avro Theme: Protocols and systems Subject: Many applications need to convert structured data to serialized form, for instance for data communication. Serialization tools such as Protobuf, Thrift, or Hadoop Avro take as input a description of a data structure, or data schema. The tools then produce methods to encode to and decode from binary representation, including things like getters and setters to access individual fields. Possible essay projects:
References:
Supervisor: Mads Dam Title: Hadoop Theme: Protocols and systems Subject: Apache Hadoop is a large and complex framework for building large scale, reliable distributed systems including database support for large tables in the style of Google's bigtable, a distributed file system, systems management tools, and an implementation of Google's MapReduce framework for processing large amounts of data in parallel. Each of the Hadoop subprojects easily offers study material for several essay projects, and can cater for both students that are practically and theoretically inclined. Project ideas:
References:
Supervisor: Mads Dam Title: Mechanical Turk Theme: Protocols and systems Subject: Mechanical Turk (or Mturk) is a work infrastructure, provided by Amazon, that allow people to perform quick tasks over the web for a small payment. The tasks (called "HITs", "Human Intelligence Tasks") are typically things that computers do poorly, like tagging pictures or assessing the effectiveness of commercial slogans. The people that perform the tasks (the "Workers"), sign in and choose a HIT they like and are qualified to do. The business that has created the task (the "Requester") checks the quality of the performed work, and pays the helper if the work is well done. Possible essay project:
References:
Supervisor: Johan Boye Programming LanguagesTitle: Software model checking using BLAST or SPIN Theme: Programming languages Subject: Model checking is based on the idea of automatically traversing a program execution graph to determine some desired property such as: Is there a way for program line 47 to be executed? Will execution eventually terminate? Does the equation x = y^2 - tmp always hold? Since these problems are generally undecidable, answers cannot be guaranteed, neither can they be guaranteed to be obtainable in reasonable time. Even so, with good engineering and using suitable abstractions, good results can nonetheless often be obtained. Examples of model checkers are BLAST, for C programs, and SPIN which is mainly applied to communications software or protocol modeling. Project ideas: The goal of an essay project on software model checking would be to learn a model checking tool such as BLAST or SPIN and apply it to a selected application. Many examples exist in the literature which can serve a suitable starting points. It would be possible, for instance, to start from a worked example and augment it step by step by adding some additional features. It is important to keep in mind that complexity often increases very quickly, so by adding features simplifications of the existing code/models will very often be needed. So small increments are highly recommended. References:
Supervisor: Mads Dam Title: Call by contract and SPEC# Theme: Programming languages Subject: In the call-by-contract paradigm, methods, objects, and classes are equipped with contracts - formal assertions - that describe how they are expected to behave. For instance, methods may be equipped with pre- and postconditions to determine properties that should be established upon method entry, resp. exit. Much work has been been done to realize such contract-oriented programming frameworks over the past 10-15 years. A well-known example for Java is the Java Modeling Language, JML, for which a number of prototype tools have been developed. See the reference below. Another example is SPEC# which extends the C# programming language with contracts. A related project is Code Contracts, also at Microsoft Research, which uses Microsoft's common intermediate language format to support contracts in a more language-independent way. Project ideas: Projects can be defined based on one of the JML tools, SPEC#, or Code Contracts. Many other tools with similar functionality exists, including some developed here. A suitable project will be to select one of the above tools and learn it well enough to apply it to a selected application. Given the time available for the work, it is better to start from something modest and add complexity, than the other way around. One possible outcome for the ambitious might be to produce a lab suitable for a future advanced programming languages course. References:
Supervisor: Mads Dam Title: Go wiki Theme: Web apps/Programming languages Subject: The hottest programming language today, Go, was launched by Google recently. It is being hyped and down-talked to the extent that testing it seems to be the only way to get un unbiased opinion. Areas where Go claims to be particularly strong are concurrent programming, web applications and rapid development. This project aims at testing and evaluating these claims. Project highlights:
References:
Supervisor: Henrik Eriksson and Stefan Nilsson Title: A nineteen tone scale synth Theme: Web apps/Programming languages Subject: ChucK is a new (and developing) audio programming language for real-time synthesis, composition, performance, and now, analysis. As far as is known, it has only been used for music using the traditional scale with each octave being divided into twelve tones. Theoretical considerations suggest that dividing the octave into nineteen parts might be a fascinating alternative. However, no such instrument exists. The goal of the project is to explore the opportunities of this new scale. Project highlights:
References:
Supervisor: Henrik Eriksson Title: ABS -An experimental object-based programming language Theme: Programming languages Subject: ABS is an experimental object-based programming language at a level of abstraction somewhere between UML and Jav. ABS is being developed in the EU project HATS. The theory group is involved in several aspects of ABS language use, design, and implementation. Currently a language definition for a core part of ABS is available, along with prototype compilers and other tools. At KTH we are currently developing a compiler/virtualization layer for ABS with the goal of allowing programs execute efficiently on a highly dynamic network and dynamically adapt to changes in operating conditions. There are opportunities for defining a number of small projects of a size suitable for an essay project in the context of this work.
References:
Contact: Mads Dam or Karl Palmskog in the theory corridor Supervisor: Mads Dam Title: Go, Erlang and F# Theme: Programming languages Subject: With the increasing multi core processor PC available today, functional languages has gained popularity. Go is a new language developed by old C/Unix designers with built in concurrency support (basically a unix pipe construct). Erlang (1982) is a revived programming language used by Ericcson, Klarna (online payment company) and others. Erlang has built in concurrency that also support scaling on several machines. F# was developed from ML, an old functional language, and is promoted by Microsoft on the .NET platform. Essay project proposal:
References: Supervisor: Alexander Baltatzis Language TechnologyTitle: Linguistic steganography Theme: Language technology Subject: Steganography is the technique of hiding secret messages. For instance, if one writes a message with lemon juice on a piece of paper, the paper looks blank until it is heated, when the message magically re-appears. Another example is the technique (used during the second world war) of shrinking a text to a tiny dot, and then hiding the dot on top of a full stop in an innocuous letter. A recent twist of the same idea is linguistic steganography, where secret machine-readable data is encoded as a seemingly innocuous natural-language text. This can be done either by generating the natural-language text from scratch in such a way that it encodes the secret message, or alternatively by modifying an existing text. In the latter case, the encoding is made by making cleverly substituting sentences, words or characters in the original text. Possible essay project:
References:
Supervisor: Johan Boye Title: Detecting plagiarism Theme: Language technology Subject: Plagiarism is the fraudulent act of copying parts of someone else's text and presenting it as one's own work. Plagiarism in schools and universities is a bigger problem than one might think (e.g. see the statistics presented at http://www.plagiarism.org/). Consequently, there are several tools on the market that attempts to detect plagiarism. The question is how good these tools are. Possible essay projects:
References:
Supervisor: Johan Boye Title: Automatic classification of opinions Theme: Language technology Subject: Many companies worry about their public image. Therefore it is of great interest to be able to automatically sift through blogs and articles and count the number of occurrences where the a certain product is mentioned in a positive way, and compare it to the number of times it is mentioned in a negative way. It order to do this rapidly and to a low cost, it would be preferable to use a simple classification method, provided it gives sufficiently accurate results. One possibility is to use a "bag-of-words" approach, i.e. only take into account which words occur in the text, not their grammatical relations. Possible essay project:
References:
Supervisor: Johan Boye Title: Wizard-of-Oz studies Theme: Language technology Subject: A Wizard-of-Oz study is an experiment where people are asked to communicate with a system which they are led to believe are fully automatic, but is actually operated by a human being. In particular, this methodology has been extensively used when developing natural-language interfaces. Possible essay project:
References:
Supervisor: Johan Boye Artificial IntelligenceTitle: Self-learning game player Theme: Artificial intelligence Subject: Reinforcement learning is a technique of letting computer programs learn what actions to take in various situations simply by trying out (some of) the possible actions and observing the result. Thus, reinforcement learning is "unsupervised" -- the program learns by interacting with the environment and is never explicitly told which action is the best one. A game-playing program might use reinforcement learning to acquire its strategic knowledge. A way of bootstrapping that knowledge is to let the program play against itself. It is an interesting exercise to find out how good a program can become just by using this technique. Possible essay project:
References:
Supervisor: Johan Boye Title: Is artificial intelligence possible? Theme: Artificial intelligence Subject: The question whether or not a machine can be intelligent has been hotly debated since the inception of the term "artificial intelligence" (and indeed well before that). Some of the most outspoken opponents have been the American philosopher John Searle, known for his "Chinese Room" thought experiment, and the British matematician Roger Penrose. Possible essay project:
References:
Supervisor: Johan Boye Algorithms and ProblemsTitle: Multi-skill call centers Theme: Problem solving Subject: Modern call centers often handle a large variety of calls. When a customer calls, he is first asked to give information concerning his reason for calling. This is usually made either via a push-button interface, or an interface that employs automatic speech recognition. Once the type of the call has been identified, the call is routed to a queue serviced by dedicated service agents. On the other hand, many service agents have multiple skills and are capable of handling more than one type of call. Thus, in general the relation between call types and service agents is a many-to-many relation (i.e. calls of a given type can be handled by several different agents, and a given agent can handle serveral different call types). Due to the ever-increasing proliferation of such multi-skill call centers, their organisation and properties has become an active research area. Two of the problems studied by computer scientists and mathematicians is the staffing an routing problems:
Possible essay project:
References:
Supervisor: Johan Boye Title: Analysis of voting algorithms Theme: Algorithms Subject: Parliament seats are to be divided proportionally to the parties, but also proportionally over Sweden. Many algorithms exist for optimizing the solution to this problem and different countries employ very different algorithms. A rational choice is possible only when the outcome of the competing algorithms has been computed for many political situations. The goal of the project is to program two or three algorithms and study their behaviour in different situations. Parameter tweaking is particularly interesting. Project highlights:
References:
Supervisor: Henrik Eriksson Title: Clustering Theme: Algorithms Subject: Investigate use of different clustering algorithms for classification on relatively large data sets. Possible uses include recognition of hand written characters and classification of articles. References:
Supervisor: Mikael Goldmann Title: Bio computing Theme:Algorithms, biological models of computation, NP-completeness Subject: In the mid 1990s, Len Adleman wrote a paper on the notion of using DNA to perform computations to solve NP-complete problems. The basic idea is that by using a large number of different DNA molecules one can examine many possible solutions to a problem in parallel. A number of papers have investigated this option as well as related options, using bacteria rather than DNA strands. A possible projects is to study articles on DNA computing or bacterial computing, explain how it works, give examples, perhaps showing how some problem not investigated in the literature can be solved. References:
Computer GraphicsTitel: Partikelsystem, Flockbeteende Tema: Datorgrafik Ämne: Partikelsystem bygger på modellering och visualisering genom att användning av ett större eller mindre antal partiklar som kan ge bilder av t.ex. fyrverkerier, rök, vattenkaskader etc. Tekniken kan också användas för att modellera flockbeteenden hos t.ex. fåglar som tilldelas vissa egenskaper för att hålla ihop, undvika kollisioner etc. Möjliga kandidatprojekt:
Referenser:
Handledare: Lars Kjelldahl Titel: Borttagning av skymda ytor Tema: Datorgrafik Ämne: Att ta bort skymda ytor är ett klassiskt problem inom datorgrafik. Problemet är alltså att man har en geometrisk modell av 3D-objekt, men ingen information om vad som är synligt när man betraktar objekten från en viss punkt. Vid utritningen av objekten på skärmen måste man ta reda på vad som syns och ska ritas ut och vad som inte syns och alltså inte ska ritas ut. Möjliga kandidatprojekt:
Referenser: Handledare: Lars Kjelldahl Titel: Grafik med begränsade resurser Tema: Datorgrafik Ämne: Mycket dagens utveckling går mot bärbar utrustning, bl.a. i form av mobiltelefoner. Grafik blir allt vanligare och självklart men de bärbara utrustningarna innebär vissa problem med små skärmar, begränsad minnes- och processorkapacitet, batterikapacitet mm. I framtiden kan vissa av dessa problem minskas eller elimineras, men t.ex. den begränsade skärmstorleken är svårare. Möjliga kandidatprojekt:
Referenser: Handledare: Lars Kjelldahl Titel: Perceptuella aspekter på datorgrafik och visualisering Tema: Datorgrafik Ämne: Perception spelar roll för vad man ska visualisera i samband med datorgrafik. En vanligt förekommande standardteknik är att rita objekt på långt avstånd med lägre upplösning. Den tekniken kallas för ”level of detail” (LOD). Möjliga kandidatprojekt:
Referenser:
Handledare: Lars Kjelldahl SimulationTitle: Event based vs. activity based simulation Theme: Web apps/Programming languages Subject: An office building obviously needs lifts but how many, how large and how quick? Such questions may be studied by computer simulation of lifts and people involved. For specific lift parameters and employee parameters, the simulation results will tell you such things as average waiting times at rush hours. In activity based simulations, time moves in small steps with all ongoing activities being updated. Activities are the movements of lifts and people. In event based simulations, time moves from one event to the next event. Events are instantaneous, such as a button being pressed or the lift arriving. Random events have to be implemented differently in the two paradigms and the whole program structure is quite different. Which of the two paradigms is best in a particular case? The goal of the project is to try to answer that question by programming the same model in the two different ways. Project highlights:
References:
Supervisor: Henrik Eriksson |