As CPU executes, information flows.

Title: As CPU executes, information flows.
Temporal information flow control - trusting timely execution

I. Introduction
Reliability and trustworthiness are two of the most important principles in modern computer systems design. It is important not only for financial companies, but also for governments, military, and every individual living in digital era. For trust computing, a system is built from a very reliable trust computing base and each system component has to be constructed with a trust chain so that the behavior of system and sensitive user information can be controlled with high-level of integrity and confidentiality. In many trustworthy computing systems design, information flow control is widely used as a major access control mechanism.

Existing information flow control (IFC) schemes focus on the direction of information flow. Namely, it prevents information from flowing to an unintended or undesired direction. In order to control the direction of information, a reference monitor observes the information flow and performs admission control.

However, existing information flow control cannot capture the notion of temporal properties of information flow. This paper presents a new perspective to information flow control, temporal information flow control. Temporal information flow control (Temporal IFC) identifies the temporal property of information flow so that a system manages information in a temporally sound manner.

Temporal IFC enables to build more reliable and trustworthy computing base. We can more strictly restrain unintended information flow with more fine-grained behaviors control. Although contemporary trust platform module (or TPM) provides validation for a platform, it lacks in dynamic behavior control. Since TPM uses a statically generated key, it cannot capture dynamic behavior of program execution.

This paper focuses on the fact that information leak usually happens with valid directional information flow. Most attackers tackle pathological weak points that cannot be easily traced by defenders. Namely, they steal information via valid path, and store the information for later use. In terms of temporal information flow control, information flow is valid only for temporally sound behaviors. So, information cannot be abused by malicious user even though it is exposed. TPM is one of such efforts, but is never a perfect solution since it uses a static key, and once key is stolen, secrecy and integrity can be broken. Temporal IFC maintains time-varying key that is very unpredictable, so it makes very difficult to abuse information with replay-like attacks.

Besides security perspectives, this paper is trying to find a pin-point where trustworthy computing meets real-time and time-sensitive information. In perspective from temporal IFC, integrity for information is regarded as broken when the information flows at temporally invalid time instant. Similarly, in a real-time system, data processing after deadlines are regarded as invalid, and the temporal integrity of information is broken. In such systems, data handling has to be finished within a specific amount of time since the data is valid temporarily. Temporal IFC tries to explain the scheduling-related information flow with derivative properties so that we can guarantee temporal behavior of program execution.

Paper is organized as following. Section 2 presents several related works. Section 3 defines temporal information flow control and properties. Section 4 explains ...

II. Related work
[Scheduling and Temporal information flow control]
[Stochastic/Probabilistic theoretic approach - Queuing theoretical interpretation for temporal information flow control]
[Real-time scheduling approach - Derivative properties for temporal information flow control]
[Instruction scheduling approach - micro-architectural instruction execution scheduling]
[Information theoretic interpretation of scheduling]

III. Temporal information flow control

[Basic idea for information flow control]
Information flow in a computer system can be defined by the propagation of information from one place to another. As program executes, values of registers, memory values, cached data are changed, which implies the information is propagated.

[Information flow control for trustworthy computer system]
Trustworthiness in existing computer systems depends on the accurate information flow in order to guarantee integrity, confidentiality of private information. The system behavior is strictly controlled by the reference monitor that resides inside an operating system so that it can observe all private information flow within a target system. The reference monitor controls the admissions to access from unreliable and untrusting users, and selectively grants operations by its policies. The information flow control thereby restricts the unintended information flow by leaks in a target system.

[Challenges in Temporal Information Flow control]
Unfortunately, information flow is difficult to control practically since memory access is widely open to every instruction in modern computers. Although modern computer architecture support ‘protected mode’ in order to protect memory from untrusted user applications, operating system, which runs in protected mode, has become too large to be statically analyzed. Moreover, behavior can also be changed dynamically at runtime (by dynamic kernel modules) and it is almost impossible to tracking all the kernel variables by time.

Temporal information flow control is more difficult than traditional information flow control because information flows by every instruction, and it is extremely difficult to control the timing of every instruction execution. Modern computer architectures support pipelining and out-of-order execution, so it is almost impossible to control the execution at instruction level. Instead, this paper focuses on the level of granularity that can be manageable at operating system.

[Limitations of existing information flow control]
Although existing reference monitor-based information flow control schemes capture important trustworthy properties in information flow, but they do not provide any notion of temporal validity of information flow. We observe that information leaks can be temporally incurred, and claim that temporal information flow should also be guaranteed for higher level of trustworthiness.

Most attackers focus on leaking information since the obtained information can be reused in most cases. For example, stack overflow attacks are making use of invalid temporal information flow. Stack frame stores the location of former stack frame, and user can access historic behavior of execution by traversing the stack frames. By carefully observing this historic behavioral pattern, attacker can get much information than expected such as values of local variables, indirect pointer values of newly allocated objects, etc. Although recent IFC approaches use taint-based integrity checks, it is still allow to access and trace private information.

By notion of temporal IFC, private information is secured by temporal key (or timed key). Since the key changes by time, and the entropy of the key is very high, so it is very difficult to get information once key is lost. Our timed key is inspired by one-time password system. In one-time password system, any password is only available at the moment of transaction, and never be utilized at any other time. In the system, information flow is secured by temporal property since the information is only available at the moment of transaction, and invalidated by time. Even though the password is intercepted by a malicious user, intercepted information cannot be used anymore. This paper realizes the notion of time-varying key, and temporal IFC with architectural support.

Furthermore, we apply the notion of temporal IFC to trustworthy computing in real-time systems. Task execution within a real-time system has temporal execution condition. Namely, a real-time task has deadline that the task has to be finished. Deadline miss can significantly degrade performance for soft real-time system applications, or incurs system failure for hard real-time systems. In order to meet deadline, a real-time task should be timely executed. In terms of information flow control, the system guarantee that information flow should be guaranteed temporally; information flow after the temporal deadline is not validated, and the integrity of the information is regarded as broken. So, trustworthiness in a real-time system implies that the program execution is sound in terms of information flow not only by direction, but also by temporal timeliness.

[Real-time scheduling and temporal information flow]
Temporal information flow control resembles the scheduling of tasks, in nature. Since scheduling within an operating system determines task/thread to execute, which implies to select instruction streams to execute. Namely, scheduling within operating system controls the temporal information flow by choosing instruction streams at processor.

In order to have a valid information, processing for the information has to be finished within a deadline. It involves the notion of real-time scheduling so that it guarantees the deadline of OS tasks. Note that important system events have to be explicitly triggered with time information.

IV.        The operation of Temporal IFC
In this section, we explain the operation of Temporal IFC. For temporal IFC, we use timed key mechanism. Timed key is established with the following three steps. At first, a timed key has to be installed at the beginning of the operation. Secondly, data has to be securely acquired from device to processor. Thirdly, the raw data is encrypted by the key and opened to memory. Once a temporal key is established, runtime validation is performed so that the information user can preserve the integrity and confidentiality. Key has to be updated in cases when the data is transferred to another task. So, this section presents temporal key establishment, runtime validation of secure information, and key update for temporal IFC. As an example, we explain the temporal IFC by network packet processing in simple real-time operating system.

[Establishment of Timed Key]
A timed key has to be generated at beginning of the operation. Basically, all tainted data (e.g. incoming network packets) are encrypted with this key so that the information is only available with the associated timed key.

When an interrupt occurs, the hardware generates a new timed key. The key is generated with the current timestamp, and stored only inside the processor so that it cannot be easily exposed to other malicious users. Processor maintains the temporal key table which associates object and timed key. At the time of generation, target execution routine (interrupt handler) is stored instead of object since there is no associate object. At the beginning of interrupt handler, the registered key index is handed as a parameter. Note that, the key is not exposed to other software.



At the beginning of interrupt handler, data have to be acquired from device. For data acquisition without CPU operation such as DMA, data is directly moved to processor’s internal memory instead of main RAM so that the user data are not opened to memory without the control of processor. In most cases, packet data is delivered via DMA, and secure DMA function delivers data from NIC to cache or transactional memory inside processor.

Recent direct cache access (DCA) can be used for secure data delivery from device to processor with perfect control of processor. When DCA is applied, data is moved from driver to cache directly with the help of new snoop protocol. Because data are placed in cache, CPU can access data immediately after delivery and can begin encryption even before it is written to main memory. For ARM-based processors, TCM(Tightly-coupled memory) is widely available, and DMA to TCM is possible. So, it similarly works with embedded processors.



Just after getting data from NIC, packet data is security is validated inside the processor. Namely, it is encrypted with timed key. At here, temporal key table is updated so that the secrecy of the object is associated with the given timed key. Note that most operations are run within cache, and cacheline is invalidated after encryption is finished since it can be exported to memory with strong protection.



[Runtime Validation of Secure Information Flow]

Once secure key is established, OS can safely deliver information with strong protection. All data are encrypted with secure timed key, and only available to a user within a given deadline. Since data have been encrypted, it cannot be properly interpreted before decrypted. Decryption logic has to be implemented in hardware and the protected information has to be isolated from untrusted/unsafe code.



Architecturally, we define a Secure Segment, in which all data are safely accessed via platform protection mechanism. All data access to secure segment is required to have proper privilege level. Since all data in secure segment are encrypted, CPU operation which touches the segment involves decryption.

We note that even though secure segment guards the access from untrusted code, register operation can still bypass the protection boundary, and storing register value to untrusted area can leak the information. Even though the code should have a proper privilege level, and should be accessible to secure segment in a sound manner, it may lead to unintended information flow. By Bell-Lapadula’s multi-level security model, higher security level subject cannot write lower security level object since higher security level subject can leak information that only he is responsible to manage.

We architecturally implement multi-level security model, and prevent information leak using memory and register access. In addition to secure segment, we adopt trusted mode, which can access the secure segment. When the processor enters trusted mode, then processor denies all memory write access to insecure segments (not-secure segment) as described above. In addition, trusted mode uses banked registers, so register values in secure segment cannot flow to insecure registers.



For untrusted mode, memory access is permitted for read/write for only insecure segments. Once encrypted, data is securely stored inside secure segment. Since the key is only available temporarily, and stored inside the processor, it cannot bypass protection boundary. In addition, any software routine cannot decrypt and access to the information without temporally valid key.

The key is valid during task to handle the information, and should be invalidated. So, the integrity is preserved within a task execution. However, in many cases, OS tasks co-operate each other and the information flows over task boundaries. In order to handle information flow that cross over task boundary, the timed key has to be hand-over so that another task can manage time-sensitive information.

When hand-over is triggered, then the processor generates a new timed key for the next task execution, and cypher text is re-encrypted with new key. So, a new key is required in order to access the data, and old information is not valid after the hand-over.

Finally, when the information is consumed by the end-user, the information has to be invalidated immediately so that it cannot be re-used, and abused by malicious user. In this case, trust for the information is broken, and can never be revoked. The data is pushed to insecure segment without protection, and the processor destroys the entry in the key table.



[Time-Varying Key : The Key maker function]
In our temporal IFC, timed key plays an important role since all data access is performed with timed key, which is temporally changing key value. It is difficult two folds: firstly, the key has to be changed by time so that the attacker cannot guess or predict the key value, secondly, the key value has to be unchanged until the corresponding task finishes its job; otherwise, all valid information flow generates false-positive alerts.

So, timed key should not be changed for the corresponding task execution, and should be time-varying so that the key value cannot be used for different time instants except for the corresponding task execution.

We achieve both goals by generating time varying key. Time varying key is generated from the internal and invisible clocksource. High bits of the timer clock source specifies the hash key to look up the timed key in the temporal key table. Low bits of the timer clock source generates randomized timed keys. We observe that high bits are changing smoothly than lower bits, so it is easier to specify the time duration for task execution. On the other hands, low bits are very sensitive to time instant that physical events occurs, which is very unpredictable. So, we use the low-bits for random source, and high bits to give time-variants. For multiple data handling at the same time instant, the table maintains Tag bits for exact matching the address for the data.
At the operation time, after passing the secure segment logic, data has to be decrypted and the plain text is given to the banked register of trusted mode. In order to decrypt the cypher text, the processor fetches time value from clock source, and finds the temporal key table with high bits. After that, the address of the data is matched within tag bits in temporal key table so that it ensures the valid timed key is used for the accessing data. Finally, the timed key is obtained from the table, and performs decryption and move the plain text into register.



%[Example]
%We explain the temporal IFC by network packet processing example. For validating the temporal integrity of information, OS routines are invoked with timestamps. For example, NetISR (network interrupt service routine) is called with not only the registers, but also timestamp. Then, the ISR can validate the packetdata by timestamp. Once it is validated, then the designated routine begins to work with packetdata. It can be orthogonally work with other taint-based approaches at here. Each packetdata has its deadline, so OS should be able to schedule the designated task properly.

%Timestamp also have to be properly protected; otherwise the information is easily leaked by hacking the timestamp values. For mandating IFC and securely protecting timestamp, we take advantage of hardware. The H/W platform should include store and record all hardware events with timstamps. The timestamp is not accessed by user-level programs, and only available at specified points. The time-related information is provided via special-purpose register. OS then checks integrity by time-shuffled key which is stored in hardware.

%In order to keep temporal integrity continuously, the system repeatedly invalidate information by task granularity. For example, the information at NetISR is invalidated at IPTask/TCPTask (or ProtocolTasks) and user task.

%For preserving the integrity of the information, inter-task communication also has to be involved with temporally valid key information. Namely, key information has to be stored by OS so that receiving task can properly decrypt (and handle) the original information.

엄마를 부탁해 - 진한 느낌의 뮤지컬

어제 뮤지컬 ‘엄마를 부탁해’를 관람했다. 워낙 잘 알려져 있는 소설인데다 최근에 미국에서도 성공적인 데뷔를 했다고 해서 관심을 갖고 있던 차에, 정말 고맙게도 처제의 뜻밖의 티켓 선물로 아내와 같이 볼 기회가 생긴 것이다. 아내와 같이 공연장을 찾은 것이 얼마만인지.. 연말 공연이라도 예매해야겠다는 다짐을 하고 충무 아트 센터에 도착한 시간은 6시 반. 공연은 7시 반이라, 저녁 식사 시간의 빠듯한 시간도 있었다. 저녁 식사를 마치고, 공연장으로 올라갔다.

뮤지컬은 처음부터 극적으로 계속 고조되는 형태였다. 어머니를 잃어버리다니! 충격으로 시작된 극은, 나머지 가족들을 중심으로 그려져 가고 있었다. 아들과 딸들, 아버지의 후회와 자책으로 이어지고 있지만, 그 안에서 우리 가족을 발견하고는 나도 몇 번이나 목이 메었다.

특히, 아들에 대한 애틋한 어머니를 표현한 아들의 회상 신은 마치 내가 어머니를 그 자리에서 꼭 찾아야만 할 것 같은 느낌을 주었다. 내 자취방 시절이나, 최근 이사온 우리 집 생활이 극 중에서 오버랩되면서, 아들의 입장과 느낌이 고스란히 내게 전해졌다. 데면데면한 아버지의 모습이나, 엄마와의 특별한 감정을 갖고 있는 여동생의 모습도, 많은 극 중의 디테일이 내 기억에서 현실로 바뀌었고, 정말 머릿 속이 복잡다양한 생각으로 꽉찼다..

1막이 정리되고, 불이 들어왔다. 아내는 옆에서 많이 울었다. 워낙 감수성이 풍부한 사람인지라, 안 울 수가 없었을게다. 자리가 살짝 비어있길래 조금 더 편한 자리로 자리를 옮겼다. 옮긴 좌석에선 얼굴과 음향감독도 볼 수 있었다. 막간을 통해 전화를 하지 않을 수 없었다. 어머니에게.. 안받으신다. 현실에는 늘 그자리에 계신 어머니가 길을 잃으신 건 아닌지. 동생에게 대신 안부전화를 넣고 위로할 수 밖에.

2막은 어머니의 일생으로 초점을 맞췄다. 내 어머니의 일생과 목표, 꿈, 시집살이와 자식과 식구들이 모르는 어머니의 삶이 그려졌다. 지난 해 어머니 자서전을 집에서 본 기억이 났다. 내 어머니도 글쓰기를 좋아하시는 문학 소녀적 감성이 풍부한 분이셨는데.. 정작 당신이 자작 일기를 책으로 편집 하실 때는 내가 너무 무심히 지나갔던 건 아닌지.

뮤지컬이란 장르는 특성 상 음악으로 스토리를 끌고 가게 되는데, 너무 무겁게 진행이 되자 사실 마음이 편하진 않았다. 청중들의 감정선을 계속해서 극단으로 몰아붙이는, 그래서 청중에게도 힘든 극이었다. 연기자들도 그만큼 힘들겠지. 이런 극을 매일 하려면, 아주 강인한 사람이어야 할 것 같다.. 극을 하면서 울 수도, 그렇다고 감정을 걷어내고 연기할 수도 없을테니..

극 후반으로 들어서자 특히 어머니의 걸음걸이나 말투가 연기하시는 김성녀씨에게서 너무 똑같이 나타나고 있었다. 눈치채기 어려운 전라도 사투리와 문어체가 살짝 섞인 말투, 그리고 걷는 모양, 얼굴 분장까지 너무 똑같은 느낌이 들었다. 이제 참기 힘든 지경이다.

극에서 어머니는 돌아오지 못한다. .. 그리고 보니, 제목이 마음에 들지 않는다. 어머니를 부탁해 - 누가.. 누구에게 부탁한 건가. 아버지가 자식들에게 어머니를 부탁한 것 까지는 그렇다 치자. 자식들도 누군가에게 어머니를 부탁하고 있다. 갑자기 여기서부터 화가 났다. 대체 자식들이 부모를 누구에게 부탁한단 말인가. 아내는 그냥 받아들이라고 했지만.. 매우 답답해졌다. 청중에게 부탁했던 것인가.. 왜 작가는 극에서 어머니를 무책임하게 버리는 선택을 했을까. 비극적인 장치라고 하기엔, 너무 내게 현실적으로 다가왔다. 마치 가까이의 누군가가 어머니를 잃어버리고, 이제 난 모르겠으니 누군가에게 부탁한다고 도피한 느낌이다. 아... 내가 화가 난 이유는, 그게 내 모습이 아니길 바라기 때문이다.

간만의 뮤지컬 공연 관람이 끝나고 집에 돌아오면서, 아내와 그런 얘기들로 공연을 되씹었다. 전체적으로 무겁게 진행되는 마음 불편한 극이라는 것이라는 것과 스토리가 무책임한 자식을 조명하며 끝나는 점이 아쉽긴 했지만, 간만에 감성을 충전한 느낌이다. 처제~ 고마워요~. 어머니 사랑해요~.

Congruence in virtualization

<behavioral congruence within virtualization>

In a virtualization environment, task execution is difficult to be analyzed. Since virtualization layer hides all the physical operations and exposes only a small subset of hardware, the actual physical behavior under the virtualization layer can be largely different from the observed behavior over the virtualization layer. For example, all task execution within a guest OS is based on the virtual time of the guest OS; however, the actual execution with physical time is differently presented, and real-time applications would miss physical deadlines, which makes difficult to incorporate real-time OSs within virtualization.

To present behavioral equivalence within virtualization, event serialization is definitely not enough. Even though events occurs consecutively in the same order, it cannot catch the timeliness of the execution. Timed automata or timed Petri-net tried to address timely execution; however, they also have limitations with respect to the state space. Since they project all the execution behavior to every time instants, the state space increases as much as the execution time. This makes difficult to analyze behavior deterministically since the halting problem is a well-known decidability problem, which is NP-hard. Namely, those timed analysis techniques are too complex, hence they are not directly applicable in scalable virtualization system.

To address timeliness within virtualization, I think, we can use the notion of real-time schedulability. Within a virtualization system, physical execution of a task is determined by the hypervisor instead of a guest OS, so a guest OS cannot impose task execution at a specific physical time instant. Namely, timeliness is difficult to define with a single time instant. Instead, we focus on the execution within a time duration. If a task is executed in a physically timely manner, then it should be executed not too late. Schedulability guarantees that tasks within a system meet deadlines, which means tasks are executed ‘not-too-late’.

In traditional real-time scheduling theory, schedulability tests are defined with a task set and scheduling algorithm. Schedulability tests determine whether all tasks can complete their execution within respective deadlines through the algorithm. For example, if tasks in the set are periodic, and the summation of their utilization is not more than 100%, then all tasks are schedulable with EDF (i.e. EDF schedulable).

In a virtualization system, schedulability of a task is difficult to define since scheduling is performed at two different levels. At first, inter-VM scheduling (or VCPU scheduling) is performed at the virtualization layer (inside a hypervisor). Secondly, intra-VM scheduling (or task scheduling) is separately performed over the virtualization layer (inside the guest OS). Inter-VM scheduling is performed by the hypervisor that doesn’t have any task information inside a guest OS. Instead of scheduling each tasks within guest OSs, the hypervisor simply schedules VCPUs that are given to each virtual machine. To schedule VCPU, each VCPU requires scheduling a parameter that represents all the execution of a guest OS.

Intra-VM schedulability is not easily determined because task execution is determined not only by task set and intra-VM scheduling algorithm, but also by inter-VM scheduling parameter of the guest OS, and inter-VM scheduling algorithm. This
Inter-VM schedulability can be easily determined provided that the scheduling parameters are given.

Does mobile phones give more freedom to people?

Small essay for writing practice

Recently mobile phones are widely used by a lot of people. Although there is a controversy, I think mobile phones have provided more freedom to people. There are two specific reasons why I think mobile phones give more freedom.

First, mobile phones free people’s communication from a fixed physical location. Even though a telephone enables a person to communicate with another at distance, the person has to be at a specific location that the telephone is installed. On the contrary, with mobile phone, one can make or receive phone call while moving places. Thus, people can work more efficiently overcoming the limitation of physical location. For example, important business decision can be made in a car, or urgent meeting can be arranged in an airplane.

Second, using a mobile phone, one can put/get useful information to/from Internet with respect to a location in a timely manner because recent mobile phones provide location-free Internet connection. For example, navigation service in your mobile phone helps you to find the shortest or the least congested path to the destination when you are traveling a new place. Besides, you can post a movie clip during a travel to Internet through a mobile phone. The media is immediately shared among people who are connected to Internet, and it provides more realistic information. So, people don’t need to rely upon the mass media such as newspaper or news broadcast. This implies that mobile phone serves as a new media service platform, and enables people to freely distribute useful information without the help of mass media.

In conclusion, mobile phones have been developed for free communication in terms of location, and helps people to work more efficiently. Furthermore, it frees people from the limitations of current mass media. Personal news or useful local information can be easily shared with the help of recent mobile phones.

Game-theoretic approach vol. 3

To testify the assumption, we measure fairness and latency satisfaction. With the current credit scheduler, we run two domains: dom1 and dom2. dom1 has both I/O and CPU load, and dom2 has only CPU workload. By changing the CPU workload (0, 20, 40, 60, 80 and 100%), we observe the characteristics of the scheduler. Fairness is measured by the throughput (amount of work done during unit time), and latency is measured by the percentage of missed deadlines.

Air way plan

Itinerary:

From Incheon to Paris,
From Paris to Wien,
From Wien to Incheon

Vienna
to meet opera or classical music

I had not been to concerts for a long time
This year, anna-sophie has come to Korea, but I couldn’t go
Sorry for my un-attendance

Wish to meet magic flute at vienna