Today is the international data privacy day!
Privacy is the ability to control the conditions under which personal information is disclosed to others. It is your right!
Protect your privacy.
Respect the privacy of others.
Maintain good online conduct as it has consequences. Remember once you have something online it is difficult to take it off and your online profile is who you are!
Online privacy by Parry Aftab:
Privacy and Social networks by PrivacyComm:
Wednesday, January 28, 2009
Monday, January 26, 2009
Facial attractiveness in binary?
Ever thought about what makes a face attractive? Is it merely physical features (symmetry, averageness, etc.) or something more to it (consciousness for example - you have a good perception about that person)? Here's an interesting read up appeared in Science News where scientists in many disciplines try to unfold the mysteries behind it; and some in computer science have even been working to make computers learn and then label faces just like how humans perceive beauty.
Sunday, January 25, 2009
Cricket..
(Source: cricinfo.com)The delighted Murali, after playing a huge role with bat (not with ball this time!) to win the final against Bangladesh in a recent triangular series involving Sri Lanka, Zimbabwe and Bangladesh. Sometimes win comes to you from the most unlikly sources in an unexpected manner..I always think that you need to have the ability plus some amount of luck to achieve your goals.
Cricket..
(source: cricinfo.com)A very young fan from Saint Kitts & Nevis greeting the ex-captain of England Kevin Peterson after getting a century in a warm up match yesterday..
Saturday, January 24, 2009
Living safely [Part 2]
Starting from where left off last time, this blog entry tries to understand liveness and safety in computer science and open room for discussion. As I mentioned in the previous blog, every (I emphasize the word "every") problem specification is an intersection of liveness and safety properties.
What exactly is a liveness property or a safety property? Lamport introduced the general notions in his "Proving the Correctness of Multiprocess Programs" (1977) paper. We can model the solution for a problem specification as a sequence of atomic actions. We use the term "execution" to refer to a sequence of actions. An execution could be a set of transactions executed on a database system, or a program you have written using a language of your choice, or a set of file operations (read, write, delete, open, close, etc.) performed on objects (files, folders) in a file system, etc. A safety property stipulates that some bad thing does not happen during execution. A liveness property stipulates that a good thing happens (eventually) during execution. [85, Alpern and Schneider]
Safety - in general, what ought not happen
Liveness - in general, what out to happen
If an execution is not a safety property, at some point its execution some bad thing must happen and that bad thing must be irremediable as a safety property never give way for a bad thing to happen. Also note that it does not require that something happen sometime and hence any execution is safe so long as we don't execute that execution. Therefore, we need something else to complement safety property. That something else is liveness property. (more on it later)
Some classical examples:
1. mutual exclusion (bad thing - two processes executing in a critical section at the same time)
2. deadlock freedom (bad thing - deadlock)
3. E1 not happening before E2 where E1 and E2 are two events (bad thing - E1 happening before E2)
Most of the time, when QAing what we test for is safety bugs. The unit test cases we have written assert something is not false. (side question: What about liveness bugs?) In other words, a safety property for a sequential program stipulates that it will never produce a wrong result. We some time call this "partial correctness". Why? As mentioned above, safety property alone is not sufficient to validate a program. (Safety properties do not stipulate that programs are loop free and terminate)
A key point about safety properties is that the violation of a safety property has a finite witness. (In terms of execution sequences, there is a prefix of the execution where we can spot the safety violation irrespective of whether the sequence is finite or infinite)
Now you should be convinced that safety property alone is not sufficient. That's where liveness properties come to our rescue.
As the definition above, liveness properties specify desirable system bahviours which must be satisfied eventually, but not always satisfied. Notice the terms "eventually" and "not always". We may not be able to observe the liveness property with a partial execution, but it remains possible for the required good thing to occur in the future. Theoritically speaking we need to monitor an infinite execution to tell if an execution violates a liveness property. It is a hard thing to do. The fundamental issue is that "eventually" does not specify any time limit. Therefore liveness is always an approximation to the property that we would like to see in the system in question.
Some classical examples:
1. Starvation freedom (good thing - making progress - each process gets to enter the critical section eventually)
2. Reliable unicast (good thing - guaranteed service, every message sent is eventually received; this actually has safety properties associated with it as well)
In practice, we need approaches where we detect liveness violations in finite executions. Using hueristics is one possibility; we may not be able to detect all the violations, but if we can make sure there no false positives at least it could be an agreeable solution. I am sure there should be some research work in this area, but I haven't looked at the research literature yet.
In addition to the questions put forward in my previous note, there are many other interesting questions as well. If something is not a liveness property is it always a safety property (or vise versa)? What is the connection between temporal logic and liveness/safety? Safety and liveness under benign failures?..Feel free to comment on the subject.
What exactly is a liveness property or a safety property? Lamport introduced the general notions in his "Proving the Correctness of Multiprocess Programs" (1977) paper. We can model the solution for a problem specification as a sequence of atomic actions. We use the term "execution" to refer to a sequence of actions. An execution could be a set of transactions executed on a database system, or a program you have written using a language of your choice, or a set of file operations (read, write, delete, open, close, etc.) performed on objects (files, folders) in a file system, etc. A safety property stipulates that some bad thing does not happen during execution. A liveness property stipulates that a good thing happens (eventually) during execution. [85, Alpern and Schneider]
Safety - in general, what ought not happen
Liveness - in general, what out to happen
If an execution is not a safety property, at some point its execution some bad thing must happen and that bad thing must be irremediable as a safety property never give way for a bad thing to happen. Also note that it does not require that something happen sometime and hence any execution is safe so long as we don't execute that execution. Therefore, we need something else to complement safety property. That something else is liveness property. (more on it later)
Some classical examples:
1. mutual exclusion (bad thing - two processes executing in a critical section at the same time)
2. deadlock freedom (bad thing - deadlock)
3. E1 not happening before E2 where E1 and E2 are two events (bad thing - E1 happening before E2)
Most of the time, when QAing what we test for is safety bugs. The unit test cases we have written assert something is not false. (side question: What about liveness bugs?) In other words, a safety property for a sequential program stipulates that it will never produce a wrong result. We some time call this "partial correctness". Why? As mentioned above, safety property alone is not sufficient to validate a program. (Safety properties do not stipulate that programs are loop free and terminate)
A key point about safety properties is that the violation of a safety property has a finite witness. (In terms of execution sequences, there is a prefix of the execution where we can spot the safety violation irrespective of whether the sequence is finite or infinite)
Now you should be convinced that safety property alone is not sufficient. That's where liveness properties come to our rescue.
As the definition above, liveness properties specify desirable system bahviours which must be satisfied eventually, but not always satisfied. Notice the terms "eventually" and "not always". We may not be able to observe the liveness property with a partial execution, but it remains possible for the required good thing to occur in the future. Theoritically speaking we need to monitor an infinite execution to tell if an execution violates a liveness property. It is a hard thing to do. The fundamental issue is that "eventually" does not specify any time limit. Therefore liveness is always an approximation to the property that we would like to see in the system in question.
Some classical examples:
1. Starvation freedom (good thing - making progress - each process gets to enter the critical section eventually)
2. Reliable unicast (good thing - guaranteed service, every message sent is eventually received; this actually has safety properties associated with it as well)
In practice, we need approaches where we detect liveness violations in finite executions. Using hueristics is one possibility; we may not be able to detect all the violations, but if we can make sure there no false positives at least it could be an agreeable solution. I am sure there should be some research work in this area, but I haven't looked at the research literature yet.
In addition to the questions put forward in my previous note, there are many other interesting questions as well. If something is not a liveness property is it always a safety property (or vise versa)? What is the connection between temporal logic and liveness/safety? Safety and liveness under benign failures?..Feel free to comment on the subject.
Thursday, January 22, 2009
Living safely
Let me warn you before I further talk about the $subject. It is from a technical point of view that I am looking at the $subject.
Have you ever thought what it would be like in real life to "live without safety" (e.g.: living in a zone where violence are frequent) or "be safe without actually living" (e.g.: living inside a cell at all times)? I am quite sure many of you have experienced one or the other, or at least heard about horrifying stories. No one would disagree with me that these scenarios are far from acceptable for any normal person. We ideally want both. We want to live and be safe (aka live safely).
It is no different in the technical world. I am referring to liveness and safety properties. "safety without liveness" will always hold as nothing happens to make it unsafe but there is little point having it in the first place (If a missile that is said to never miss the target is always safe so long as it is not fired - but what is the point of having it if it is not utilized). "liveness without safety" is dangerours as it may result in loss/damage to systems, people or other tangible and intangible items (what if there are traffic signals at a four way junction that turn green at the same time, what if there is an air traffic control system that allows two planes to land on the same run way, what if when you withdraw $20 from an ATM it goes on to deduct $200, and the like).
It took me some time to realize that every real problem specification is a combination of both liveness and safety properties. Some of the queries you might have are..
What does it actually mean that a system is safe or live? Do we have universal notions of them?
Do liveness and safety properties relace or complement one another?
Can we prove that every specification is a combination of both?
How do we prove a system is live or safe or both?
What does it mean that a program we have written is safe and/or live?
How do we identify safety or liveness bugs in a system?
What is the theoritical foundation for these properties?
Do these concepts relate to soundness and compleness?
and the list of questions goes on..
I will answer the above questions and more in another blog entry soon.
Have you ever thought what it would be like in real life to "live without safety" (e.g.: living in a zone where violence are frequent) or "be safe without actually living" (e.g.: living inside a cell at all times)? I am quite sure many of you have experienced one or the other, or at least heard about horrifying stories. No one would disagree with me that these scenarios are far from acceptable for any normal person. We ideally want both. We want to live and be safe (aka live safely).
It is no different in the technical world. I am referring to liveness and safety properties. "safety without liveness" will always hold as nothing happens to make it unsafe but there is little point having it in the first place (If a missile that is said to never miss the target is always safe so long as it is not fired - but what is the point of having it if it is not utilized). "liveness without safety" is dangerours as it may result in loss/damage to systems, people or other tangible and intangible items (what if there are traffic signals at a four way junction that turn green at the same time, what if there is an air traffic control system that allows two planes to land on the same run way, what if when you withdraw $20 from an ATM it goes on to deduct $200, and the like).
It took me some time to realize that every real problem specification is a combination of both liveness and safety properties. Some of the queries you might have are..
What does it actually mean that a system is safe or live? Do we have universal notions of them?
Do liveness and safety properties relace or complement one another?
Can we prove that every specification is a combination of both?
How do we prove a system is live or safe or both?
What does it mean that a program we have written is safe and/or live?
How do we identify safety or liveness bugs in a system?
What is the theoritical foundation for these properties?
Do these concepts relate to soundness and compleness?
and the list of questions goes on..
I will answer the above questions and more in another blog entry soon.
Tuesday, January 20, 2009
Relationship among notions of security for encryption schemes
While reading some security papers, I came across the following diagram and explanation [1]. It sums up the relations among commonly used notions of security for public-key encryption schemes.
The goals = { IND, NM }
The attacks = { CPA, CCA1, CCA2}
The notions = goals * attacks = {IND-CPA, IND-CCA1, IND-CCA2, NM-CPA, NM-CCA1, NM-CCA2 }
Let A and B be any two any two notions from the above set.
A => B holds if X is any encryption scheme meeting the notion of security A then X also meets the notion of security B. (In other words, B providers stronger notion of security compared to A)
In the above diagram there is an arrow (normal or hatched) if and if implication between two security notions holds.
Refer to [1] for more information.
[1] Relations Among Notions of Security for Public-Key Encryption Schemes, 1999, M. Bellare et.al.
The goals = { IND, NM }
The attacks = { CPA, CCA1, CCA2}
The notions = goals * attacks = {IND-CPA, IND-CCA1, IND-CCA2, NM-CPA, NM-CCA1, NM-CCA2 }
Let A and B be any two any two notions from the above set.
A => B holds if X is any encryption scheme meeting the notion of security A then X also meets the notion of security B. (In other words, B providers stronger notion of security compared to A)
In the above diagram there is an arrow (normal or hatched) if and if implication between two security notions holds.
Refer to [1] for more information.
[1] Relations Among Notions of Security for Public-Key Encryption Schemes, 1999, M. Bellare et.al.
Subscribe to:
Posts (Atom)