Thesis Ideas

From Thumper

Primary Choices

• Extend average reward timed games work
• specification, metaprogramming, automated programming
• applying a formalism (game theory?) to forensic analysis
  • One paper I read showed how you can use MAC-times to discover the approximate timing of illicit privilege escalation, because of the broken invariant "files are modified by users that are logged in". The advantage to this is that it's like an intrusion detection system; you might not have timing information, but this allows you to discover it.
  • A different way to use MAC-times is to remove from consideration all files which are "explainable" in some non-violation way. This might be considered a form of semantic integrity checking, but demands correlating with long-running daemons (cron, etc). It is more useful when applied to process audit logs, rather than MAC-times.
  • Along the "explainable" lines -- it would be nice to be able to examine the computer memory and make sure everything is explainable there.
  • The other paper I read allowed you to describe evidence discovered in terms of the state of "the system". But you needed to be able to encode each possible hack into the system, which might not be exhaustive. I'm not sure how this could be practical in real life.
  • What forensics really needs now is some kind of logic system that allows you to postulate hypothesis and check for contradictions. One thing you need to postulate: how far the system clock is from another clock (for instance, when correlating to a NIDS log)? When doing an analysis, often you start with an estimation of the time of the intrusion, and then start identifying "interesting" events and lay them out in a timeline.
  • The downfall of forensics is that increasingly sophisticated attacks will be able to leave little or no evidence.
  • One way to defeat log editing is to add a digital timestamp with the checksum of previous log data (since the previous timestamp). Of course, it is still possible to stop logging or edit the file, but now the modifications will be obvious. (Unless someone modifies the source to read the existing log on startup and recalculate the checksum... Is there a way to defeat this?)
• specification of real-time games

Other Ideas

• Regarding the ω proof of Godel's Incompleteness theorem: Is there any way to know when you have a truth that can't be proved using the existing axioms? Besides by exhaustive reasoning.
• automated negotiation: if two parties full share their utility functions, then it is possible to achieve an agreement that is optimal for both parties; is this point a nash equilibrium? (I think so.) If the parties do not share information about their utility function, how does that change? Is there a way to measure how much information is transfered in each exchange of a negotiation?
  • presumably, each party makes proposals which have a positive profit margin.
  • if a party rejects a proposal, it is either because the proposal is below their profit margin, an earlier proposal had a higher profit margin, or the party believes that they can do better against their opponent.
  • When is a negotiation over? As soon as one party makes a proposal and the other accepts? What if the proposer wants to probe variations?
  • Related to that, what about successive refinement of proposals? What if parties are negotiating on what they think are the important points, first, and then negotiate on fine points when they think these fine points have been decided?
• click fraud: how do you know which sites are responsible for click fraud in Google advertising? Is there a way to discover them?
  • Clearly, if Google reports more clicks than are being redirected to the advertiser site, then there is click fraud. Comparison with Google logs would reveal these bad actors.
• what can you do with a list of compromised computers?
  • How do you detect more compromised computers?
  • Can you model the system of attack and detection, and find optimal strategies for either?
  • Can you model the attack and find ways to detect compromised machines and control machines and peer victims?
• Can personalities in a company be modeled? Can you show people will interact? This seems like a far-fetched idea, because what are the inputs and outputs? What are you trying to measure? How do you know when a "computation goes wrong"?
• What is the relation between model checking (operational) and axiomatic (sets of states) reasoning? Can we combine both techniques to get more specific results?
• Can a language be defined where you can't write a program that doesn't terminate (charity), except for I/O? Aaron contends that there is only one non-terminating patter: the event loop.
• Look further into the Curry-Howard isomorphism. Yes, programs are proofs of a type morphism, but are they a proof of anything else? Is the computation just a side-effect? Review "Putting Curry-Howard to Work".
• Can reversible computation be useful? What are people doing? What can you calculate this way?
• backwards debugging: given a function result, how far backwards can you go? Can this be used to find where a computation goes wrong?
• would a debugging that understands pre and post conditions be more useful?
• can we model the laws of our society, and then compose them to discover loopholes and contradictions? (Like in programming, the real problem is that you need a specification of what loophole you are searching for. I don't see how this part can be automatically discovered.)
• can we visualize academic papers from an area of research? Does this reveal lines of research? Can we use this to guess the future direction of research? can we use Google Trends to decide how competing lines of research are faring?
• how is Kolmogorov complexity being applied to compression?
• is there a probabilistic form of Fourier analysis? (Notice the weak connection to compression.) Can this be used to predict host uptimes, or file access times, or user login times?