Yi Liu
email: yi.liu@jsi.buaa.edu.cn

Xinwei Zhang

Yonghui Wang

Depei Qian

Yali Chen

Jin Wu

Partition-based Hardware Transactional Memory for Many-core Processors

Keywords: Transactional Memory, Partition, Many-core

Transactional memory is an appealing technology which frees programmer from lock-based programming. However, most of current hardware transactional memory systems are proposed for multi-core processors, and may face some challenges with the increasing of processor cores in many-core systems, such as inefficient utilization of transactional buffers, unsolved problem of transactional buffer overflow, etc. This paper proposes PM_TM, a hardware transactional memory for many-core processors. The system turns transactional buffers that are traditionally private to processor cores into shared by moving them from L1-level to L2-level, and uses partition mechanism to provide logically independent and dynamically expandable transactional buffers to transactional threads. As the result, the solution can utilize transactional buffers more efficient and moderate the problem of transactional buffer overflow. The system is simulated and evaluated using gems and simics simulator with STAMP benchmarks. Evaluation results show that the system achieves better performance and scalability than traditional solutions in many-core processors.

Introduction

Among works to improve programmability of parallel systems, transactional memory is an attractive one. Compared to traditional lock-based programming models, transactional memory can improve programmability, avoid deadlock and furthermore, promote performance of concurrent programs. Most of current hardware transactional memory (HTM [START_REF] Herlihy | Transactional Memory Architectural Support for Lock-Free Data Structure[END_REF] ) systems are proposed for multi-core processors, and may face some challenges with the increasing of processor cores in many-core systems: firstly, utilization of transactional buffers are inefficient since those buffers are private to processor cores while generally only part of cores execute transactions simultaneously in many-core processors; secondly, the on-going challenge of transactional buffer overflow for HTMs is still unsolved.

In this paper, we propose PM_TM, an architecture of hardware transactional memory for many-core processors. The main idea consists of two points: firstly, turns private transactional buffer into shared by moving them from L1-level to L2-level; secondly, uses partition mechanism to provide logically independent and dynamically expandable transactional buffers to transactional threads, and furthermore, to isolate access-interferences among large number of processor cores. As the result, the system can utilize transactional buffers more efficient and moderates the problem of transactional buffer overflow in many-core processors.

The rest of this paper is organized as follows. Section 2 analyzes problems of traditional hardware transactional memory in many-core environment and then gives an introduction to our solution. Section 3 presents the architecture of our proposed system. Section 4 evaluates the system with benchmarks. Section 5 introduces related works. And section 6 concludes the paper.

2

Challenges in many-core processors and our solution

Problem analysis

Most of current hardware transactional memory systems are proposed for multi-core processors, and may face some challenges in many-core systems. Firstly, transactional buffers are inefficiently utilized and resources are wasted. Traditionally, transactional buffer is located inside processor cores in parallel with L1 data cache, which means it's private for the core. Processor core accesses transactional buffer only in transactional state, i.e. on executing transactions. However, in manycore processors, there will be a large number of processor cores, and generally only small part of them execute transactions simultaneously, while most of transactional buffers are not used at all.

Secondly, Problem of transactional buffer overflow is still unsolved. Generally, size of transactional buffer is fixed in each processor cores, when a transaction reads/writes too many data, buffer overflow will occur. This "buffer overflow problem" is one of ongoing challenges for hardware transactional memory. Despite some solutions have been proposed, most of them rely on co-working between cache-level transactional buffer and main memory or virtual memory, and need complex hardware/software operations.

This problem will even cause some kind of contradictions in many-core processors. On one hand, transactional buffers are inadequate in some processor cores that cause transactional buffer overflows due to some "long transactions", while on the other hand, transactional buffers in other processor cores may not be used at all.

Our solution: an overview

Based on the above discussions, we propose an architecture of hardware transactional memory, called PM_TM, for many-core processors. In our proposed solution, the transactional buffer is "logically independent" because that the transactional cache is partitioned into multiple partitions, each of them corresponds to one transactional thread and can only be accessed by it. The transactional buffer is "dynamically expandable" because that each partition is initially allocated a buffer with basic size, and can be expanded if the corresponding thread accesses excessive data speculatively in a transaction. The advantages of the proposed solution include:

(a) Transactional buffers can be utilized more efficiently. In many-core environment, generally only part of processor cores execute transactions at the same time, that is, most of transactional buffers will be idle if they are private for cores. By turning them from private to shared, all of transactional buffers can be utilized by ongoing transactions, and the waste of resources can be reduced greatly.

(b) The problem of transactional buffer overflow is moderated. Since the transactional buffers are shared by all of the processor cores, and generally only part of cores execute transactions simultanously, by managing transactional buffers with partition mechanism and expanding partitions when necessary, a transaction can have much bigger transactional buffer than traditional private buffer. As the result, the possibilities of transactional buffer overflow are smaller.

In addition, from the implementation point of view, it is easier to integrate much bigger L2-level transactional buffer into processors than L1-level.

(c) Context switch and migration of transactional threads are easier to implement. For some long-transactions or transactions with system-calls, the operating system will suspend the transactional thread inside a transaction and schedule other threads to run on the core. After a while, the original transactional thread will be re-scheduled to run on either the same or a different core. Traditionally, this is a problem for HTMs since the transactional thread may face either a damaged or a totally new transaction context. In our proposed solution, the transactional buffer are shared by all of the cores and bound to transactional threads instead of cores, so the context switch and migration of transactional threads can be easily supported.

3

Partition-based hardware transactional memory architecture

System architecture

Fig. 1 shows the architecture of tile-based [START_REF] Moscibroda | A Case for Bufferless Routing in On-Chip Networks[END_REF], [START_REF] Bedford | Evaluation of the raw microprocessor: An exposed-wire-delay architecture for ILP and streams[END_REF] many-core processors with support of our proposed hardware transactional memory. The system is composed of three types of tiles: the first type is tiles of processor cores plus private L1 cache and routing mechanism; the second is tiles of L2 cache banks; and the third is tiles of transactional cache (TC). All of the tiles are connected with an on-chip network, and both L2 cache and transactional cache are shared by all of the processor cores. The transactional cache is used to buffer the data accessed by transactions speculatively, and as shown in Fig. 2, its structure is similar to L2 cache and data is also stored by line. The difference is that the transactional cache holds both old and new version of data for each line, where the old version is the data that the transaction started with, and the new version is the current version updated by the transaction speculatively. Detailed introduction to consistency and conflict detection are given in section 3.3.

In addition, to support efficient nesting of transactions, the system uses a partial rollback mechanism which was proposed in our previous works [11]. The mechanism uses n-bits read and write vector for each line to indicate whether the line has been read or written speculatively, with each bit in the vector corresponding to one level of nested transactions. By adding limited hardware, conditional partial rollback can be implemented, that is, when a transaction needs to roll back due to a conflict, instead of rolling back to the outermost transaction as in commonly-used flattening model, the system can just rolls back to the conflicted transaction itself or one of its outerlevel transactions if given conditions are satisfied.

Fig. 2. Structure of transaction cache

In architecture level, transactional cache is in parallel with L2 cache. Commonly a processor core accesses L2 cache, and once a transaction is started, it switches to access transactional cache in order to guarantee that all the speculative accessed data are buffered and not valid until commit of the transaction.

Partition mechanism

(1) Overview Partition mechanism is a method to manage hardware resources in multi-/manycore processors. In our proposed system, partition mechanism is used to establish multiple logically independent transactional buffers, i.e. partitions, in shared transactional cache, furthermore, to make these transactional buffers dynamically expandable. In the system, transactional caches are allocated to partitions in partition-unit (PU) which corresponds to multiple successive lines in the transactional cache. Each partition corresponds to one transactional thread, and is created with one PU initially that can expand to multiple successive PUs if it is needed.

Partitions are created only for threads that execute transactions, called transactional thread. Once a thread executes a transaction at the first time, a partition is created with only one PU, and along with the increasing of read/write data set of a transaction, more PUs can be allocated to the partition dynamically if its transactional buffer overflows. After the commit of the first transaction, the partition is reserved and used by subsequent transactions of the thread, and finally released when the thread is finished.

It is noted that the owner of a partition is transactional thread rather than processor core. The reason is that transactional threads may be suspended during its execution and scheduled to run in another core after it is waked up later. In other words, migration of transactional threads can be supported by binding partitions with transactional threads instead of cores.

(2) Partition access When a thread starts to execute a transaction, it switches to access its transactional buffer (i.e. partition) instead of L2 cache. As Fig. 3 shows, an associative buffer is used to store information of partitions including starting address, partition size and owner thread, with each entry corresponding to one partition. Based on this hardware infrastructure, the transactional buffer of a thread can be located quickly by means of the thread ID. (3) Partition management As mentioned above, a partition starts with one PU and may expand along with the execution of the transactional thread if excessive data are accessed in a transaction speculatively, and to simplify the management of partitions, it is limited that all of the PUs of a partition must be successive in transactional cache. In order to leave spaces at the end of partitions for potential expansions in the future, it's better to allocate partitions dispersedly in transactional cache.

According to above discussions, the system allocates the first partition from the beginning of transactional cache, and subsequent partitions are allocated in the following policy: searching for the biggest free area in the transactional cache, and allocating the PU in the middle of the area to the new partition.

Table .1 shows the addresses that will be allocated to partitions one by one, where B is the total size of transactional cache in lines, N is the number of processor cores, and the size of partition unit PU=B/N. A partitioning example is shown in Fig. 4. In Fig. 4(a), four partitions are created one by one for transactional thread T0--T3, and T0 has successfully expanded its partition in 1 PU; in Fig. 4(b), thread T0 and T3 finish their execution and partitions are released, after that, a new partition is created for thread T4.

In additio created a cases, the some lon cache per this time, release th LRU poli main mem partition

Co

The to each disage is retriggered, result, the corresponding transactions will abort their execution and roll back. Similarly, there also is a directory with the same structure in transactional cache. Once a line of transactional buffer is updated, an invalidate message is also sent to other sharers. (2) Conflict Detection Method to detect conflicts among transactions is: when a processor P reads/writes address A in a transaction, the cache controller sends a share-/exclusive-request to transactional cache directory, once the reply is received, it sets status of the transactional cache line to shared or exclusive; meanwhile, if another processor Q accesses address A too, the request is forwarded to processor P to identify if there is a writewrite or read-write conflict, and consequently, to approve or reject the request.

Fig. 6 shows examples of conflict detection: (a) Transaction startup: processor P starts a transaction and switches to access transactional buffer.

(b) Writing data: P writes address A0 which is not in its transactional buffer, firstly it sends a get-exclusive request to directory, which is approved with the requested data, then P stores the data to its transactional buffer and sets write-flag, finally it replies an ACK to directory.

(c) Reading data: P reads address A1 which is not in its transactional buffer, the procedure is the similar to (b) except that the request is get-shared instead of getexclusive.

(d) Transaction conflict: processor Q reads the address A0 which was just written by P, firstly it sends a get-shared request to directory, which is forwarded to P and identified as a read-write conflict, then a NACK is sent back to Q; Q deals with the conflict after receiving the NACK and replies a NACK to directory.

(e) Successful shared reading: processor Q reads the address A1 which was just read by P, the request is identified as conflict-free and approved.

Execution of Transactions

When a processor core starts to execute a transaction, it flushes data in L1 data cache and L2 cache to lower level and main memory, and switches to access transactional buffer instead of L2 cache.

During execution of a transaction, all of the data accessed by the transaction are buffered temporarily in its transactional buffer(partition). When a data is accessed for the first time in the transaction, it is loaded to both old and new version of the line in transactional buffer, subsequent updates to the data are just stored to new version, and R/W status are set at the same time.

Once the read/write-set of a transaction exceeds the partition size, a transactional buffer overflow occurs. At this time, the system tries to expand the partition by allocating one more PU in transactional cache. If the successive PU at the end of the partition is free, the partition can be successfully expanded and memory accesses are continued, otherwise it stalls for a short period of time and tries again. If there is still no free PU, the expanding operation fails and a global lock is set, the overflowed transaction continues exclusively without conflict until its commit. Of couse, the performance will be suffered in this situation.

If a transaction needs to roll back in case of conflict, data in transactional buffer are copied from old to new line by line, at the same time, R/W status are cleared, after that, all of the lines in L1 data cache are set to invalidate.

When a transaction finishes its execution and commit, all of the updated data in transactional buffer(partition) are written to main memory.

ISA extensions and programming interface

As a hardware transactional memory, PM_TM supports transparent execution of transactions with no restriction on programming languages. Only two instructions are extended to specify the start and end of a transaction, as shown in Table .2. Programmers just need to identify program statements that must be executed atomically in their applications, and define them as transactions by inserting appropriate API at the beginning and the end of each transaction.

4
Experiments and Evaluation

Experimental environment

The proposed system is simulated in GEMS [13] and Simics [14], and by extending the simulator, our partition mechanism and consistency protocol are implemented on SPARC-architecture processors in the simulator.

We evaluate PM_TM system using Stanford STAMP [START_REF] Cao | STAMP: Stanford Transactional Applications for Multi-Processing[END_REF] benchmark, and experimental results are compared with LogTM [START_REF] Kevin | LogTM: log-based transactional memory[END_REF] and a native HTM, called NativeTM, in which transactional buffers are in L1-level and private to each processor core.

Table 3 summarizes parameters of the simulated target system. The evaluation uses 4 applications that vary in size of read/write data set, length of transactions and contention degree among transactions, as in Table 4.

Results and analysis

(1) Performance Fig. 7 shows average execution time of applications in PM_TM, LogTM and Na-tiveTM with 4--128 processor cores. Each application is executed with number of threads equaling to processor cores.

We can see from Fig. 7 that PM_TM behaves not very well in less processor cores. The main reason is that access latency of transactional buffers in PM_TM is longer than others due to its L2-level location. Along with the increasing of processor cores, PM_TM achieves better performance than two other systems, since that less transactional buffer overflow occur in PM_TM, and contentions among transactions are also handled more efficient in PM_TM. Fig. 7 also shows that results of different applications are not quite the same due to their characteristics. Kmeans has not only less transactions but also small read/write data set, so there is few transactional buffer overflows during the execution. As the result, the performance of Kmeans in PM_TM is not improved by the partition mechanism, instead, the performance is influenced by the long access latency of transactional buffers. Compared with kmeans, the intruder application has bigger read/write data set and higher contentions among transaction. So PM_TM achieves better performance along with the increasing of processor cores. Vacation has almost the same size of read/write data set with intruder, but vacation has some long transactions and contention in vacation is lower than intruder. Compared to other applications, the bayes has bigger read/write data set and longer transactions. Contention is also higher than the others. (2) Transactional buffer overflows Table 5 gives transaction overflow statistics of applications in NativeTM and PM_TM. LogTM is not included in this table because transactional data of LogTM is stored in the memory directly. From the table we can see that most applications overflow less in PM_TM than in NativeTM except kmeans, which has not only less transactions but also small read/write data set. Furthermore, with the increasing of L2-level transactional cache, the overflow times reduce significantly. As discussed in section 2.2, from the implementation point of view, it is easier to integrate much bigger L2level transactional buffer into processors than L1-level buffer.

(3) Conflict and rollback Fig. 8 shows transaction rollbacks of applications. LogTM uses bloom filter [START_REF] Burton | Space/time trade-offs in hash coding with allowable errors[END_REF] to store transaction read/write data set, that may produce false-conflicts, and furthermore, the cost of abort in LogTM is much higher due to its eager version management. Compared to LogTM, PM_TM uses bit-set to record data set of transactions so that there is no false-conflict in it. And due to this reason, the number of conflicts in NativeTM is the same with PM_TM, and omitted in the figure. In kmeans, transactions are small and shared data among transactions are few, so frequency of conflict is much lower than other programs. Transactions in intruder are slightly larger than kmeans, but frequency of conflict is much higher. Although vacation has some large transactions, competition between transactions in vacation is low-er than intruder. As for bayes, PM_TM system is much better than LogTM in rollback test. Bayes has the largest R/W set among the four programs, so overflow times of bayes is the most.

Related Works

Transactional memory was firstly proposed in [1], since then, lots of hardware transactional memory (HTM) systems have been proposed that support atomicity of transactions by hardware, and achieves high performance. On the other hand, HTMs are often bounded by space and time constraints, i.e. transactional buffer overflow and transaction migration. Some solutions have been proposed to deal with transactional buffer overflow. The simplest solution is partial-commit or in-place commit which uses a global lock or things like that to prevent other transactions to commit, until commit of the overflowed transaction [START_REF] Moscibroda | A Case for Bufferless Routing in On-Chip Networks[END_REF], [START_REF] Shriraman | An Integrated Hardware-Software Approach to Flexible Transactional Memory[END_REF], [START_REF] Shriraman | Flexible Decoupled Transactional Memory Support[END_REF] . Beside partial-committing, some solutions deal with overflows by co-working between transactional buffer and memory [START_REF] Kevin | LogTM: log-based transactional memory[END_REF], [START_REF] Ceze | Bulk Disambiguation of Speculative Threads in Multiprocessors[END_REF] ; some solutions support unbounded transactions by means of complex hardware mechanism [START_REF] Scott Ananian | Unbounded Transactional Memory, 11th International Symposium on High-Performance Computer Architecture (HPCA2005)[END_REF], [START_REF] Rajwar | Virtualizing Transactional Memory[END_REF] ; hybrid transactional memory [START_REF] Kumar | Hybrid Transactional Memory[END_REF] has also been proposed, which integrates both hardware and software transactional memory, and switches to software mode in case of buffer overflow.

TM systems for many-core processors have also been proposed. TM 2 C [START_REF] Gramoli | TM2C: a Software Transactional Memory for Many-Cores[END_REF] is a software TM system which provides two services: the application service and the Distributed TM service. The former connects transaction with the application and controls the transactional runtime. The latter grants a data access to the requesting transactions through distributed locking. The main contribution of TM 2 C lies in guaranteeing starvation-freedom with low overhead.

LogTM [START_REF] Kevin | LogTM: log-based transactional memory[END_REF] is a log-based HTM system. It saves old values in a log and puts new values in target address. When transaction commits, values in target address become visible and log is abandoned directly. This will accelerate the process of transaction committing. When rollback occurs, it simply copies old values in the Log to the target address. LogTM uses directory-based Cache consistency protocol to guarantee data consistency and eager conflict detection to find conflict between transactions.

Conclusion

Transactional memory is an appealing technology to improve programmability of multi-core and many-core processors. However, most of current hardware transactional memory systems are proposed for multi-core processors, and may face some challenges with the increasing of processor cores in many-core systems: firstly, utilization of transactional buffers are inefficient since those buffers are private to processor cores while generally only part of cores execute transactions simultaneously in many-core processors; secondly, the on-going challenge of transactional buffer overflow for HTMs is still unsolved. This paper proposes an architecture of hardware transactional memory for manycore processors, called PM_TM. The main idea consists of two points: firstly, turns private transactional buffer into shared by moving them from L1-level to L2-level; secondly, uses partition mechanism to provide logically independent and dynamically expandable transactional buffers to transactional threads, and furthermore, to isolate access-interferences among large number of processor cores. As the result, the system can utilize transactional buffers more efficient and moderates the problem of transactional buffer overflow in many-core processors. The system is simulated and evaluated using gems and simics simulator with STAMP benchmarks. Evaluation results show that the system achieves better performance and scalability than traditional solutions in many-core processors.

Fig. 1 .

 1 Fig. 1. System architecture

Fig. 3 .

 3 Fig. 3. Structure of transaction cache

Fig. 5

 5 Fig. 4.

Fig. 5 .

 5 Fig. 5. Structure of cache directory

Fig. 6 .

 6 Fig. 6. Examples of Conflict Detection

Fig. 7 .

 7 Fig. 7. Average execution time of applications

Fig. 8 .

 8 Fig. 8. Transaction rollbacks

Table 1 .

 1 Address allocation of partitions

	Seq. of creation	Start address	Initial end address
	0	0	PU -1
	1	B/2	B/2 + PU -1
	2	B/4	B/4 + PU -1
	3	3B/4	3B/4 + PU -1
	4	B/8	B/8 + PU -1
	...	...	...

Table 2 .

 2 Address allocation of partitions

	Instruction	Description	Programming interface
	XB	Trans. start	BEGIN_TRANSACTION()
	XC	Trans. end	COMMIT_TRANSACTION()

Table 3 .

 3 Configuration of target system

	Processors	Ultrasparc-iii-plus, 1GHz
	Cache size	L1: 64KB L2: 4MB
	Size of cache line	64 bytes
	Memory	1GB 80-cycle latency
	Cache coherence protocol	MESI_CMP_filter_directory
	Interconnection network	Tiled NoC; X-latency:1, Y-latency:2
	Transactional cache	PM_TM: 1/2/4 MB; NativeTM: 8KB/core
	Operation System	Solaris 10

Table 4 .

 4 Applications from STAMP benchmark

	Application	R/W Set	Len. of transactions Contention
	intruder	medium	short	high
	kmeans	small	short	low
	vacation	large	medium	low
	bayes	large	long	high

Table 5 .

 5 Transaction overflows

	Application System	Transactional buffer size	4	8	Number of processor cores 16 32 64	128
		N a t i v e T M 8 K B / c o r e	0		0	0	0	0	0
	kmeans	PM_TM	1 M B 2 M B	0 0		0 0	3 2	5 3	6 5	8 6
			4 M B	0		0	0	0	2	5
		NativeTM 8KB/core	12	24	48	96	192	384
	intruder	PM_TM	1MB 2 M B	0 0		0 0	4 3	8 4	29 9	52 3 1
			4 M B	0		0	0	0	3	7
		NativeTM 8KB/core	19	33	56	131	263	477
	vacation	PM_TM	1MB 2 M B	0 0		6 0	13 7	18 1 1	45 1 8	104 4 7
			4 M B	0		0	0	5	9	2 1
		NativeTM 8KB/core	361	733	1307	1891	3249	4811
	bayes	PM_TM	1MB 2MB	173 30	267 181	661 277	1081 649	2033 1213	4795 2258
			4MB	0	24	190	307	636	1309

Acknowledgements

This work was supported by National Science Foundation of China under grant No. 61073011, 61133004, and National Hi-tech R&D program(863 program) under grant No. 2012AA01A302.


Neng Huang
email: nenghuang@hust.edu.cn

Zhiyuan Shao
email: zyshao@hust.edu.cn

Hai Jin
email: hjin@hust.edu.cn

FRESA: A Frequency-sensitive Sampling-based Approach for Data Race Detection

Keywords: Concurrency, Data Race, Sampling, Bug Detection

Concurrent programs are difficult to debug due to the inherent concurrence and indeterminism. One of the problems is race conditions. Previous work on dynamic race detection includes fast but imprecise methods that report false alarms, and slow but precise ones that never report false alarms. Some researchers have combined these two methods. However, the overhead is still massive. This paper exploits the insight that full record on detector is unnecessary in most cases. Even prior sampling method has something to do to reduce overhead with precision guaranteed. That is, we can use a frequency-sensitive sampling approach. With our model on sampling dispatch, we can drop most unnecessary detection overhead. Experiment results on DaCapo benchmarks show that our heuristic sampling race detector is performance-faster and overhead-lower than traditional race detectors with no loss in precision, while never reporting false alarms.

Introduction

Multithreading is getting more and more popular in today's software. In other words, software must become more parallel to exploit hardware trends, which are increasing the number of processors on each chip. Unfortunately, correct and scalable multithread programming is quite difficult. The instructions in different threads can be interleaved randomly. A data race occurs when two different threads access the same memory location without an ordering constraint enforced between the accesses, and at least one of the accesses is a write [START_REF] Netzer | What are race conditions?: Some issues and formalizations[END_REF]. Data races are not necessary errors in and of themselves, but they indicate a variety of serious concurrency errors that are difficult to reproduce and debug such as atomicity violations [START_REF] Lu | Avio: detecting atomicity violations via access interleaving invariants[END_REF], order violations [START_REF] Lu | Learning from mistakes: a comprehensive study on real world concurrency bug characteristics[END_REF], and sequential consistency violations [START_REF] Manson | The java memory model[END_REF]. As some races occur only under certain inputs, environments, or thread schedules, deploying low-overhead and precise-coverage race detection tool is necessary to achieve highly robust deployed software.

There has been much effort to develop automatic tools for detecting data races. Ultimately, the detection techniques are broadly categorized according to the time they are applied to the program: static and dynamic. Static techniques [START_REF] Henzinger | Race checking by context inference[END_REF][START_REF] Naik | Effective static race detection for java[END_REF][START_REF] Pratikakis | Locksmith: context-sensitive correlation analysis for race detection[END_REF][START_REF] Qadeer | Kiss: keep it simple and sequential[END_REF][START_REF] Sasturkar | Automated type-based analysis of data races and atomicity[END_REF][START_REF] Voung | Relay: static race detection on millions of lines of code[END_REF] provide maximum coverage by reasoning about data races on all execution paths. However, they tend to make conservative assumptions that lead to a large number of false data races alarm. On the other hand, dynamic techniques [START_REF] Dinning | Detecting access anomalies in programs with critical sections[END_REF][START_REF] Elmas | Goldilocks: a race and transaction-aware java runtime[END_REF][START_REF] Flanagan | Fasttrack: efficient and precise dynamic race detection[END_REF][START_REF] Pozniansky | Efficient on-the-fly data race detection in multithreaded c++ programs[END_REF][START_REF] Schonberg | On-the-fly detection of access anomalies[END_REF][START_REF] Yu | Racetrack: efficient detection of data race conditions via adaptive tracking[END_REF][START_REF] Zhai | Carisma: a context-sensitive approach to racecondition sample-instance selection for multithreaded applications[END_REF] are more precise than static tools, but their coverage is limited to the paths and thread interleaving explored at runtime. In practice, the coverage of dynamic tools can be increased by running more tests.

Most dynamic data race detectors are not widely used due to their runtime overhead. Data race detectors like RaceTrack [START_REF] Yu | Racetrack: efficient detection of data race conditions via adaptive tracking[END_REF] incurs about 2x to 3x slowdown and Intel's Thread Checker [START_REF] Sack | Accurate and efficient filtering for the intel thread checker race detector[END_REF] takes performance overhead on the order of 200x. Such large performance overhead leads to the lack of data race detectors used in practice. The main reason for this very large performance overhead is each memory operation executed by the program needs to be recorded and analyzed. LiteRace [START_REF] Marino | Literace: effective sampling for lightweight data-race detection[END_REF] uses sampling to reduce the runtime overhead of data race detector. It presents a sampling algorithm which based on the cold-region hypothesis that data races are likely to occur when a thread is executing a "cold" (infrequently accessed) region in the program. PACER [START_REF] Bond | Pacer: proportional detection of data races[END_REF] shows a "get what you pay for" approach that provides scalable performance and scalable odds of finding any race. It provides a qualitative improvement over prior approaches.

This paper presents a frequency-sensitive sampling-based approach called FRESA. FRESA makes a precise and coverage guarantee: no matter what sampling methods you used, it learns and updates its sampling strategy intelligently. In other words, "get what you want but pay for less".

FRESA collects and organizes historical sampling results for the next sampling. In order to make the sampler more effective, it owns a finding density table in each schedule path. Compared with previous table, FRESA computes and creates a sampling probability interval, which helps making a more appropriate proportional sampling rate.

The rest of the paper is organized as follows: section 2 introduces our motivation and section 3 describes our algorithm. In section 4, we show our experimental results and performance. We list some related work in section 5. Then we conclude our current work and future work in section 6.

Motivation

We We have an instrumentation in DaCapo eclipse. Figure 1 lists a random selected 200 sequential accesses frequency. Access frequency imbalance is quite obviously as shown. Previous race detection methods based on sampling never take it into account. Obviously, quite a lot overhead could be reduced through asymmetrical sampling rate.

FRESA Algorithm

In order to leverage the asymmetry. This section presents our FRESA algorithm. FRESA is a dynamic data race detection sampling method based on happenbefore relationship, which uses a frequency statistics for the next time's sampling based on asymmetrical access information.

FRESA starts at a user-given sampling rate r 0 for every shared memory in sampling areas. It collects shared memory access frequency at run time. With the program execution, different shared memory's access frequency appears different. FRESA groups all the memories into different groups by considering their access frequencies. As more and more different memories grouped, each group can have a unique sampling rate based on user-given sampling rate. FRESA believes that the more frequently the shared memory accessed, the lower proportion the shared memory could have a data race. Since data races that occur in frequently accessed memory of well-tested programs either have already been found or fixed.

Frequency Statistics

FRESA collects the frequency of a memory location accessed, with the aim of grouping the memory of similar access frequency into the same group. By this means, different memories can be partitioned into different groups. FRESA assigns different sampling rates to different groups.

FRESA uses a hashtable to maintain variables access frequency information. We define the memory location x in hashtable as a tuple (siteId, frequencyNum). siteId refers to the call site at which x is allocated and f requencyN um stands for the access frequency of x. We update the hashtable after every access using the algorithm below. With the program execution, the hashtable updates at run time. Assume we get a hash map contains n different accesses x 1 , x 2 , x 3 . . . x n and with the relevant access frequencies f 1 , f 2 , f 3 . . . f n . In a general way, we first simply divide our n tuples into 5 groups.For an empirical practice, we set four group frequency threshold as g 1 = 20, g 2 = 50, g 3 =100, g 4 = 200. For each (x i ,f i ), we dispatch it into a group in the following formula:

Algorithm 1 Hashtable Update Algorithm

(x i , f i ) ∈            G 1 f i ≤ g 1 G 2 g 1 < f i ≤ g 2 G 3 g 2 < f i ≤ g 3 G 4 g 3 < f i ≤ g 4 G 5 f i > g 4 (1)
We only list a simple piecewise function above. The group threshold can be different in practice due to the different frequency distribution.

Adaptive Sampling

FRESA does the same thing as PACER either in sampling periods or nonsampling periods. During sampling periods, FRESA fully tracks the happenbefore relationship on all synchronization operations, and variable reads and writes, using FASTTRACK algorithm. In non-sampling periods, FRESA also reduces the space and time overheads of race detection by simplifying analysis on synchronization operations and variable reads and writes. However, FRESA adaptively changes its sampling rate using variable access frequency information. As for one access x, sampling rate r is decided by variable group classification as the following formula:

r xi = F (g j |r 0 ) x i ∈ g j ( 2
)
where r xi indicates the proper sampling rate for access x i . F (g j |r 0 ) defines the sampling rate for group g j .

In our experiment, we use an exponential decline equation r xi = r 0 /2 j x i ∈ g j (j = 1, 2, 3, 4) in our example.

Theoretical Accuracy and Slowdown

Table 1 summarizes the effect of FASTTRACK, PACER and FRESA have on (1) the detection rate for any race and (2) program performance for sampling rate r and data race occurrence rate o. Constant c rw is the slowdown due to analysis at reads and writes, and c sync n is the linear slowdown in the number of threads n due to analysis at synchronization operations. PACER essentially scales FASTTRACK's overhead by r, as well as a small constant factor c sampling due to PACER's additional complexity (e.g., indirect metadata lookups). PACER adds a slowdown c non-sampling during non-sampling periods, which is small and near-constant in practice. In FRESA, constant c ′ rw is a little bigger than that in PACER as shared memory's access frequency information update.

Performance Evaluation

Implementation

FRESA is implemented in Jikes RVM 3.1.01 , a high-performance Java-in-Java virtual machine [START_REF] Alpern | Implementing jalapeño in java[END_REF]. FRESA is built on PACER's source code 2 . We execute all experiments on a Pentium Dual-Core CPU E5300 @2.6 GHz system with 2 GB main memory running openSUSE Linux 3.4.6-2.10. We used the multithreaded DaCapo benchmarks [START_REF] Blackburn | The dacapo benchmarks: Java benchmarking development and analysis[END_REF] (eclipse, hsqldb, and xalan; versions 2006-10-MR1). The range of sampling rates we use in our experiments is [0.000625, 1], and we set the minimum user given sampling rate r min = 0.01. As data races occur infrequently and sampling decreases the probability of observing a race, we do many trials to evaluate accuracy.

Effectiveness of Data Race Detection

Figure 2(a) and 2(b) show FRESA's detection rate versus sampling rate for each benchmark. Figure 2(a) counts the average number of dynamic evaluation races per run that FRESA detects. A race's detection rate is the ratio of (1) average dynamic races per run at sampling rate r to (2) average dynamic races per run with r = 100%. Each point is the average of all evaluation races' detection rates. The plot shows that FRESA reports races at a somewhat better rate than the sampling rate. However, this may have some different observations in different executions.

Time and Space Overheads

Time overhead. Figures 3 shows the slowdown incurred by FRESA on each benchmark for r ranging over [0, 100%]. The graphs show that FRESA has overheads that scale roughly linearly with the target sampling rate, although the slowdown factors on different benchmarks vary a lot. The slowdown factor in this experiment includes the execution time of the program, the overhead incurred by the JikesRVM platform, the overhead incurred by dynamic memory access and synchronization instrumentation and the overhead incurred by the sampling algorithms. FRESA incurs slowdowns by a factor less than 3x on three benchmarks (eclipse, hsqldb, xalan) at a target sampling rate of 1%, and can detect races with a relatively higher probability (80%) than PACER. When working at a target sampling rate of 100%, FRESA has no sampling effort and is functionally equivalent to FASTTRACK [START_REF] Pratikakis | Locksmith: context-sensitive correlation analysis for race detection[END_REF]. In this scenario, FRESA slows down the three programs by a factor of 10x on average, compared with 8x by FASTTRACK and 12x by PACER. Though FRESA uses hashtable leading to little more access time, it still incurs less time overhead than PACER due to the saving of sampling cost. Space overhead. Figure 4 shows the maximum live memory space overhead incurred by FRESA with various FRESA configurations. The measurement includes application, VM, PACER, and FRESA memory. For each target sampling rate shown, we take the mean overhead over all executions. Base shows the max memory used by eclipse running on unmodified Jikes RVM. OM only adds two words per object and a few percent all-the-time overhead. The other configurations (except LITERACE) are PACER and FRESA at various sampling rates. At a sampling rate of 100%, FRESA takes no differences as PACER. At other sampling rates, FRESA uses significantly less memory than PACER. The result shows that FRESA can scale well with the sampling rate in terms of memory space used, and with a low sampling rate of r = 1%, its space overhead appears to be very low.

Related Work

A large part of researches [4-11, 16, 17, 19-22, 24-31] focus on dynamic or static race detection. Dynamic race detection techniques are either based on lockset or on happen-before or hybrid of them. Lockset based dynamic techniques could predict data races that does not happen in a concurrent execution which leads to report many false warnings. Happen-before based techniques detect races that actually happen in an execution. Therefore, these techniques lack of good coverage though precise. On the other hand, happens-before based race detectors cannot predict races that could happen on a different schedule or they cannot create a schedule that could reveal a real race. In practice, the coverage can be increased by running more tests. Recently happens-before race detection has been successfully extended to classify harmful races with sampling. Hybrid techniques combine lockset with happens-before to make dynamic race detection both precise and predictive. But these techniques also report many false warnings. Static race detection techniques provide maximum coverage by reasoning about data races on all execution paths. However, they tend to make conservative assumptions that lead to a large number of false data races.

In general, the traditional methods using vector clocks takes O(n) time and space overhead, n is the number of threads. The FASTTRACK algorithm replaces most O(n) analysis with O(1) analysis with precise guaranteed. However, these methods still incurs significant overhead.

A novel approach that explores the above tradeoff is sampling. LITERACE uses a sampling dispatch to decide whether to sample synchronization events only or together with all memory access of a function. On the other hand, PACER uses a more effective sampling strategy. It divides an execution into a scenario of sampling or non-sampling periods. PACER can detect race in a magic shortest data race way and with a probability of r. This significantly reduces the slowdown overheads.

A common limitation of the above techniques is that although existing precise sampling-based data race detectors such as PACER and LITERACE can effectively reduce overheads so that lightweight precise race detection can be performed efficiently in testing or post-deployment environments, they are ineffective in detecting races with much unnecessary repeated sampling cost. Our insight is that along an execution trace, a program may sample some raceinfrequently variable in high sampling rate. These unnecessary sampling cost potentially indicate a saving cost degree in a sampling region. Intuitively, they may perform redundant memory access sampling, which lowers the chance of detecting rare data races and costs more unnecessary sampling overhead.

Recently, a couple of random testing techniques for concurrent programs have been proposed. These techniques randomly seed a program under test at shared memory accesses and synchronization events. Although these techniques have successfully detected bugs in many programs, they have two limitations. These techniques are not systematic or reproducible. Many researchers look for effective sampling method to solve this problem.

Conclusions and Future Work

Data race is a common problem in multithreaded program. It often indicates serious concurrency errors which are easy to introduce but difficult to reproduce, discover, and fix. Prior approaches reduce overhead by sampling. But they waste too many cost on repeated checking which can be omitted or reduced. In other words, frequency statistical sampling strategy could be more effective with detection precise guaranteed. This paper presents a data race detection method that provides a detection rate for each memory location that has inverse relationship with access frequency, and adds less time and a little more space overheads than PACER. FRESA achieves a qualitative improvement over prior work: its access frequency based sampling strategy suits more comfortable for performance and accuracy sensitive program, which makes it more suitable for all-the-time use in a variety of deployed environments. Our future work should simplify happen-before relationship and optimize the instrumentation with a lower cost level. In addition, we could generalize the approach to deal with different types of bugs caused by frequently access and develop new methods to further refine the approach.

Fig. 1 .

 1 Fig. 1. A random selected 200 sequential accesses in DaCapo eclipse.

  FRESA's accuracy on distinct races.

Fig. 2 .

 2 Fig. 2. FRESA's accuracy on dynamic and distinct races.

Figure 2 (

 2 Figure 2(b) shows the detection rate for distinct races. If a static race occurs multiple times in one trial, this plot counts it only once. The detection rate is much higher because FRESA's main concept of memory access frequencysensitive, which means infrequent accesses have more sampling cost.

Fig. 3 .

 3 Fig. 3. Slowdown vs. sampling rates

Fig. 4 .

 4 Fig. 4. Max live memory for eclipse

motivate our work by a common program shown below.

		void func3(int x){
		test3 += x;
		}
	}
	public class TestTest{
		Test test = new Test();
		Thread t1 = new Thread(){	//thread t1
		public void run(){
		for(int i = 0; i < 10000; i++)
		test.func1(1);
		test.func2(1);
		test.func3(1);
		}
		}
		Thread t2 = new Thread(){	//thread t2
		public void run(){
		test.func1(1);
		for(int i = 0; i < 100; i++)
		test.func2(1);
		test.func3(1);
		}
		}
		Thread t3 = new Thread(){	//thread t3
		public void run(){
		test.func1(1);
		test.func2(1);
		test.func3(1);
		}
		}
		public static void main(){
		t1.start();
		t2.start();
		t3.start();
		t1.join();
		t2.join();
		t3.join();
	public class Test{ }
	}	int test1,test2,test3;
		void func1(int x){
		test1 += x;
		} In the program the shared memory test1, test2, test3 are accessed 10002,
	void func2(int x){ 102, 3 times respectively, which shows an asymmetrically accessed distribution
	test2 += x; by thread1, thread2 and thread3. The asymmetry like the above program is quite
	} common in real applications.

Table 1 .

 1 Theoretical accuracy and slowdown

		Det. race	Slowdown
	FASTTRACK	o	crw+csyncn
	PACER FRESA	o × r ∑ m i=1 oi × ri	c sampling (crw + csyncn)r + c nonsampling ∑ g i=1 c sampling (c

′ rw + csyncn)ri + c nonsampling

http://dacapo.anu.edu.au/regression/perf/2006-10-MR2.html

http://www.jikesrvm.org/Research+Archive

Acknowledgements

Thanks to the anonymous reviewers for feedback on this work. This work is supported in part by the National High-tech R&D Program of China (863 Program) under grant No.2012AA010905.


Bo Xie
email: xiebo@nudt.edu.cn

Geming Xia
email: xiageming@126.com

Yingwen Chen
email: csywchen@gmail.com

Ming Xu
email: xuming@nudt.edu.cn

Roadside Infrastructure Placement for Information Dissemination in Urban ITS Based on a Probabilistic Model

Information dissemination is an important application in VANETs for traffic safety and efficiency. In urban area, roadside infrastructure nodes can be deployed for information dissemination. However, it is inefficient and uneconomical to cover the whole urban area. How to find the optimal locations to place DPs is a research problem. Some works on this issue have to collect accurate trajectories of all the vehicles, which is not practical in the real environment. In this paper, we propose a novel approach for DPs placement in grid road networks without knowing trajectories. Based on the analysis of path number between two intersections, a probabilistic model is proposed to get the trajectories estimation of vehicles. The theoretical optimal algorithm (OA) and two heuristic algorithms (called KP-G and GA) are developed for the problem. Simulation results reveal that GA is scalable and has the highest coverage ratio on average.

Introduction

Information dissemination based on Vehicular Ad hoc Networks (VANETs) is intended to the support traffic safety and efficiency, as well as services for drivers [START_REF] Dikaiakos | Vitp: an information transfer protocol for vehicular computing[END_REF][START_REF] Mak | Amulti-channel vanet providing concurrent safety and commercial services[END_REF][START_REF] Yang | A vehicle-to-vehicle communication protocol for cooperative collision warning[END_REF]. In this paper, we deal with information dissemination from roadside infrastructure to passing vehicles, tackling the specific issue of deploying an intelligent transport system infrastructure that efficiently achieves the dissemination goal. For example, transport department can disseminate some traffic news to vehicles. We refer to the vehicles who have received the disseminated information as informed vehicles. Our goal is to maximize the number of informed vehicles. In other words, we aim at maximizing the coverage ratio of information dissemination.

In principle, an information dissemination system could leverage both vehicle-tovehicle (V2V) and vehicles-to-infrastructure (V2I) communications. When only a few of roadside units (RSUs) are deployed, V2V communications could enable data sharing thus increasing the coverage ratio of information dissemination. However, the gain achieved through V2V communication strictly depends on the network topology and the particular cooperation paradigm, and it is difficult to evaluate in the general case. In this paper, we analyze the problem of optimally placing infrastructure nodes (e.g. IEEE 802.11 access points or RSUs) only considering V2I communications.

We refer to the infrastructure nodes as Dissemination Points (DPs). A DP serves for the vehicles that pass through the dissemination range of the DP. In other words, the vehicles who pass through a DP could be served (i.e., covered). However, it is difficult, in terms of infrastructure cost, to cover all roads with a large number of DPs, especially during the rollout of ITS. In our approach, DPs are placed at intersections which prove to be much better locations than road segments for DPs deployment in [START_REF] Trullols | Planning roadside infrastructure for information dissemination in intelligent transportation systems[END_REF]. We could describe this problem as follows: in a given urban area which has N intersections with a limited number of k DPs ( k N ≤ ), what is the best deployment strategy to maximize the coverage ratio of information dissemination.

We could model the problem as a Maximum Coverage Problem (MCP). However, traditional approaches of MCP may not be suitable for this problem for three reasons. First, the DPs deployed in the area neither have to necessarily form a connected network, nor provide a continuous coverage of the road topology. Second, vehicles move among these different DPs rather than be stationary. Third, vehicles may cross more than one intersection, thus they may be served by more than one DPs. The problem presented in this paper differs from traditional problems. This problem could be solved through heuristic algorithms if we could get the accurate trajectory of every vehicle as in [START_REF] Trullols | Planning roadside infrastructure for information dissemination in intelligent transportation systems[END_REF]. However, the drivers may not be willing to share their trajectories for privacy concerns. As a consequence, it is not practical to collect every vehicle's accurate trajectory for decision-making. Moreover, because the trajectories of all vehicles and the traffic pattern may change from time to time, the placement based on trajectories may not be stable. It means that the optimal placement based on a certain set of trajectories may not be optimal in another set of trajectories. Meanwhile, in real communication environments, it could not assure that a vehicle could receive the information from a DP when it passes the DP. We introduce a parameter ps to represent the probability that a vehicle could successfully receive information from a DP. The probability ps is a feature of a wireless link and may affect the deployment of DPs. Our scheme deploys DPs at the most appropriated locations based on ps rather than improving ps.

In this paper, we propose a novel approach to solve the problem without using vehicles' accurate trajectories. Instead of vehicles' accurate trajectories, we only need the road network topology, and vehicles' origin points and destination points. Note that in a certain observation time, most vehicles except taxis have specific origin points and destination points in one journey. Based on the analysis on the statistical or historical data, we could get the distributions of the numbers of vehicles at origin points and destination points. Then the trajectories estimation of vehicles could be derived. Then, we propose a theoretical optimal algorithm (OA) and two heuristic algorithms (called KP-G and GA) for the problem.

The remainder of this paper is organized as follows. Section 2 reviews the previous work. Section 3 presents a probabilistic model, and proposes an optimal algorithm as well as two heuristic algorithms. Performance evaluations are presented in Section 4. Section 5 concludes this paper.

Wireless access point or base station placement is a well known research topic. In the context of sensor networks, several studies have considered the optimal node placement schemes which are always NP-hard. To tackle such complexity, several heuristics have been proposed to find sub-optimal solutions [START_REF] Arkin | Data transmission and base-station placement for optimizing the lifetime of wireless sensor networks[END_REF][START_REF] Capone | Deploying multiple interconnected gateways in heterogeneous wireless sensor networks: An optimization approach[END_REF] in presence of stationary nodes.

In VANETs and mesh networks, there are several studies on roadside units (RSUs) placement problem. Lochert et al. [START_REF] Lochert | Data aggregation and roadside unit placement for a vanet traffic information system[END_REF] have tackled the problem of sparse roadside units placement for data aggregation but not information dissemination. Sun et al. [START_REF] Sun | Roadside units deployment for efficient shorttime certificate updating in vanets[END_REF] propose cost-efficient RSUs deployment scheme for short-time certificate updating. In this scheme, OnBoard Units (OBUs) in any place could communicate with RSUs in certain driving time, and the extra overhead time used for adjusting routes to update short-time certificates is small. Pan et al. [START_REF] Li | Optimal placement of gateways in vehicular networks[END_REF] address the problem of optimally placing one or multiple gateways in both 1-D and 2-D vehicular networks to minimize the average number of hops from APs. They also give some analytical results for finding the optimal placement of multiple gateways in 2-D vehicular grid networks and discuss how to minimize the total power consumption. Abdrabou et al. [START_REF] Abdrabou | Probabilistic delay control and road side unit placement for vehicular ad hoc networks with disrupted connectivity[END_REF] present an analytical framework to statistically estimate the maximum packet delivery delay from a vehicle to an RSU for a low density VANET via vehicle-to-vehicle communications. Aoun et al. [START_REF] Aoun | Gateway placement optimization in wireless mesh networks with qos constraints[END_REF] propose a polynomial time near-optimal algorithm which recursively computes minimum weighted Dominating Sets (DS), while consistently preserving QoS requirements across iterations. Trullols et al. [START_REF] Trullols | Planning roadside infrastructure for information dissemination in intelligent transportation systems[END_REF] have done the closest work to ours. They propose three heuristic deployment algorithms MCP-g, MCP-sz and KP-P for information dissemination in intelligent transportation systems. However, their heuristic algorithms need the accurate trajectory of every vehicle. The difference between our work and [START_REF] Trullols | Planning roadside infrastructure for information dissemination in intelligent transportation systems[END_REF] is that we could make approximate optimal DPs placement only based on road network topology and vehicles' origin points and destination points. We also consider the probability of vehicles served.

3

Probabilistic Model and Placing Algorithms

Problem Statement

We consider an urban grid road network. As in many Chinese cities, the road networks are very regular which could be mapped into grid road networks. Literature [START_REF] Trullols | Planning roadside infrastructure for information dissemination in intelligent transportation systems[END_REF] reveals that intersections prove to be much better locations than road segments for DPs deployment. Thus, we also place DPs at intersections. We assume that each DP cover only one intersection, which means that only vehicles cross it could be served (i.e., covered). Our goal is to place the k DPs for maximizing the number of informed vehicles. However, we would not need vehicle's accurate trajectories for two reasons.

As first important, vehicles may not share their trajectories for privacy concerns, and it is also impossible and unpractical to collect those sensitive individual data. On the other hand, the placements based on trajectories are not stable due to trajectories may change time to time. It is not flexible to deploy DPs in real world.

We propose a probabilistic model based on the distributions of the origin points and destination points of vehicles in an urban environment. As we know, most vehicles except taxis have specific origin points and destination points in one journey. For example, during 7:00am and 8:00am, they drive from their home to offices. Then they park their vehicles near their offices. The residence is the origin point, and the parks near offices are the destination points. While the path from origin point to destination point is uncertain for different reasons. For example, they could choose the path according to the real time traffic, or according to their favor, or by GPSbased navigation systems, and so on. We study the probability of vehicles crossing each intersection by random path selection.

Number of Paths

In a given grid road network, the number of paths between two intersections is needed to be calculated. We assume that vehicles always select the shortest paths. Traditional approaches search the shortest paths using graph theory such as Dijkstra algorithm. However, it is not sufficient for grid networks due to so many paths with the same shortest distance. As shown in Fig. 1, we assume the length of each segment is the same.

Let

1 1 2 2
FP(( , )( , )) i j i j denote the number of paths between 1 1 ( , ) i j and 2 2 ( , ) i j . To reduce the dimension of FP, we use a integer x to represent the intersection ( , ) i j in m n × grid road network, where ( 1) x i n j = -⋅ + . Therefore,

FP(( , )( , ))

i j i j could be denoted as ( , ) fp x x could be calculated as Eq.( 1).

1 2 1 1 2 2 ( ) ( , ) (( , )( , )) ( , ) ! ! i j fp x x FP i j i j F i j i j Δ + Δ = = ΔΔ = Δ Δ (1)
In Eq.( 1),

1 2 | | i i i Δ = -
,and

1 2 | | j j j Δ = -
.For example, (1,12) FP((1,1)(3, 4)) F(2,3) 10 fp = = = .

Origin Points and Destination Points

The origin points and destination points will be any places on the road segment; however, we could map these points into the intersections. For example, as shown in Fig. 2

Probabilistic Model and Algorithms

In the m n × grid network, let ( , )

k k i j denote the original address of intersection k x . Here, 1 k i m ≤ ≤ , 1 k j n ≤ ≤ and ( 1)
k k k
x i n j = -⋅ + . We introduce several probabilities as listed Table 1.

We use Coverage Ratio (CR) to evaluate the final performance of the algorithms. CR means the proportion of the number of vehicles served by DPs to the number of total vehicles during the observation time. We could use Eq.( 2) to compute CR. The probability that a vehicle is served when it crosses

x x pa
The probability that a vehicle has once appeared at

x x pg
The probability that a vehicle starts from

x x pd
The probability that a vehicle disappears at

x o d x x pod
The probability that a vehicle is start from o x and disappears at d

x x pp
The probability that a vehicle passes through the intersection x but neither starts from nor disappears at x The probability that a vehicle passes through these c intersections,

1 c > 1 1 | | i i i i i k i k x x i x x i V ps CR pa ps NVT = = = = ⋅ = < ⋅ ∑ ∪ (2)
In Eq.( 2), i x V means the set of vehicles that cross i x , and NVT means the total number of vehicles during the observation time. Therefore,

1 | | i i i k x x i V ps = = ⋅ ∪
means the total number of vehicles that have been served by one or more of DPs which are placed at these k intersections. However, it is quite difficult to compute the accurate CR. It is obvious that CR is fewer than

1 i i i k x x i pa ps = = ⋅ ∑
which could be used as approximate value and obtained with less computation. According to the above analysis, we propose an optimal algorithm OA, and two heuristic algorithms KP-G and GA. The optimal algorithm OA could only be used in small scale situations due to its high computational complexity.

The optimal algorithm OA and heuristic algorithm KP-G are listed as following, respectively.

Algorithm ...

k k pf pf pf pa - < < < < , 2
pf plays a more important role in Eq.( 2) than other c pf with 2 c > . In large grid road networks, c pf are relatively small. Therefore, in GA, we use 2 pf to approach the accurate CR. It will lose some performance comparing with OA, but it has quite low computational complexity.

We use 3 k = to explain how to compute CR with 2 pf as Eq.( 3). [START_REF] Dikaiakos | Vitp: an information transfer protocol for vehicular computing[END_REF] 1

2 2 3 3 1 2 1 1 2 1 2 2 1 3 2 1 2 2 2 3 2 1 3 2 2 3 2 1 2 2 1 3 | | ( ( , ) ( , ) ) ( ( , ) ( , ) ) ( ( , ) ( , ) ) ( , ) (1 (1
) ( 1)) ( , ) (1 ( 1) (1

i i i k x x i x x x x x x x x x V ps CR NVT pa pf x x pf x x ps pa pf x x pf x x ps pa pf x x pf x x ps pf x x ps ps pf x x ps = = ⋅ = ≈ - - ⋅ + - - ⋅ + - - ⋅ + ⋅ -- ⋅ - + ⋅ -- ⋅ ∪ 3 2 3 2 2 3
)) ( , ) (1 ( 1) (1 ))

x x x ps pf x x ps ps

- + ⋅ -- ⋅ - (3)
The heuristic algorithm GA is listed as following.

Algorithm 3 GA 1: Initialize, S φ = , 0 c = , {1,..., } U N = . 2: while c k < do 3: 1 c c = + .

4:

for every i x U ∈ do 5:

( ) i S c x = .

6: compute the CR of S as Eq.(3). 7: end for 8:

select i x that maximizes CR, ( ) i S c x = .

9:

i U U x = -.
10:end while

Performance Evaluation

In this section, we conduct simulations to evaluate the performance of the proposed algorithms. Note that, we do not concern ourselves with low-level issues in wireless communications.

In [START_REF] Trullols | Planning roadside infrastructure for information dissemination in intelligent transportation systems[END_REF], a heuristic algorithm KP-P is proposed based on the knowledge of the number of vehicles crossing each intersection. KP-P sorts the intersections in descending order by their crossing vehicles, and selects the first k intersections to place DPs. Using the trajectories generated by our simulator, we could implement KP-P. Therefore, results of KP-P could be regarded as the simulation results of our KP-G. The CR of GA, KP-G, OA, and KP-P are evaluated in this section. Therefore, we compare the four algorithms in the following subsections.

Small Scale Scenarios

In this subsection, we use small m, n, k, and we compare the four algorithms. Due to computational complexity, OA is computationally feasible only for small values of k in very small scale scenarios. We use 4 4 × grid road network as shown in Fig. 1.

When 4 k > , the computational complexity is too high to obtain the optimal solution. We give the CR of OA with 2,3, 4 k = . We use the same

x ps for every intersection. As shown in Fig. 3, we could get the following conclusions. First, both simulation results of OA and KP-G are excellently agree with the analytical results. It demonstrates the accuracy of our model. Second, GA is much better than KP-G and KP-P, and even has the same performance as OA. For a given CR, GA needs fewer DPs, and for a certain number of DPs, GA could achieve higher CR. However, with the decline of ps, the performance benefit of GA becomes more unremarkable, and the overall CRs of all algorithms become smaller. In real environment, we always attend to increase the probability ps, therefore GA is much more useful than other algorithms.

We then study the detailed placements of the four algorithms. For example, Table 2 shows the placements with 1 ps = . The integers represent the intersection sequence numbers as shown in Fig. 1. When 2 k = , the placements of the four algorithms are respectively {11, 6} , {11,10} , {10, 7} , {6,11} . When 4 k = , the placements are respectively {11, 6,8, 9} , {11,10, 7, 6} , {11, 7,10, 6} ,{4, 7,10,13} . With the increment of k, we only need to add additional points into the original sets for GA, KP-G, KP-P, whereas we have to change all the points of OA. In other words, GA, KP-G, KP-P could yield incremental placements, whereas OA has to compute the results for different k. The difference between the placements of KP-G and KP-P is not remarkable. Note that, CR of GA reaches 1 for 6 k = , whereas KP-G and KP-P both need 8 DPs for 1 CR = . For GA, the placements listed in Table 2 is not unique for 8 k = . The last two intersections could be replaced by any other intersections. × grid road network which is half of N. Because OA could not be solved within acceptable time even when 2 k = in this large network, we only compare GA with KP-G and KP-P. We generate a pair of random 6 9 × matrices of G and D which are referred to as 2 G and 2 D , and generate another symmetrical pair of matrices as 3 G and 3 D . In 3 G and 3 D , all vehicles start from and also disappear at the borders of the grid. It is an extreme special case.

There are similar conclusions with that in small scale scenarios. Furthermore, from Fig. 4, we could find that different G and D cause different performances. However, GA is still better than KP-G and KP-P. In Fig. 4(b), CRs of KP-G and KP-P have remarkable difference for some k due to its extreme special 3 G and 3 D . Whatever the different G and D are, the benefit of GA is very remarkable, especially with 3 13 k < < .

Conclusion

In this paper, we proposed a novel maximum coverage approach for disseminating information to vehicles in intelligent system in urban area without using vehicles' trajectories. We proposed a probabilistic model based on the distributions of the numbers of vehicles at origin points and destination points to get the trajectories estimation of the vehicles. We applied this model to compute the coverage ratio. Next, an optimal algorithm OA and two heuristic algorithms KP-G and GA were proposed. It was not practical to adopt OA due to high computational complexity. Our results proved that GA had better performance than the other algorithms in most of scenarios. However, we still remarked that in different scenarios with different parameters and conditions, it was better to compare the algorithms and choose the best one.

In fact, the road networks of many cities are not regular grid. We could still map the road networks into grids through some mechanisms which will be our future work. Drivers may choose paths with the different probabilities, thus other path selection models will also be considered in our future work.

1 1 1 1

 1

  Figure 1. 4 4 × Grid Road Network 1 2

Figure 2 .

 2 Figure 2. Mapping Origin Point into Intersection

Figure 3 .

 3 CR versus the number of DPs deployed, for4 4

Figure 4 .

 4 Figure 4. CR versus the number of DPs deployed, for 6 9 × grid road network, 1 ps =

Table 1 . Probability Symbols Symbol Description

 1

x ps

Table 2 .

 2 Placement of Every Algorithm

			Algorithm Placement
			GA	{11, 6, 8, 9, 3, 14, 16, 1}
			KP-G	{11, 10, 7, 6, 15, 2, 14, 8}
			KP-P	{11, 7, 10, 6, 14, 15, 2, 3}
			OA	{6, 11}, {6, 11, 16}, {4, 7, 10, 13}
	4.2	Large Scale Scenarios
	For a large grid network of 6 9 × , there are	N =	54	intersections. We study more
	DPs as	k =	27

Acknowledgment

This research is partially supported by the National Science Foundation of China under Grant No. 61070211, No. 61272485, No. 61070201 and No. 61003304; and Hunan Provincial Natural Science Foundation of China under grants No. 09JJ4034.


Shun-Te Liu

Yi-Ming Chen

Shiou-Jing Lin
email: sjlin@cht.com.twcym@cc.ncu.edu.tw

A Novel Search Engine to Uncover Potential Victims for APT Investigations

Advanced Persistent Threats (APT) are sophisticated and targetoriented cyber attacks which often leverage customized malware and bot control techniques to control the victims for remotely accessing valuable information. As the APT malware samples are specific and few, the signature-based or learning-based approaches are weak to detect them. In this paper, we take a more flexible strategy: developing a search engine for APT investigators to quickly uncover the potential victims based on the attributes of a known APT victim. We test our approach in a real APT case happened in a large enterprise network consisting of several thousands of computers which run a commercial antivirus system. In our best effort to prove, the search engine can uncover the other unknown 33 victims which are infected by the APT malware. Finally, the search engine is implemented on Hadoop platform. In the case of 440GB data, it can return the queries in 2 seconds.

Introduction

The cyber attacks become more and more sophisticated. Recently, this kind of targetoriented, covered and long-term attacks is labeled as advanced persistent threat (APT) [START_REF] Daly | The Advanced Persistent Threat[END_REF][2][START_REF] Hpgary | [END_REF][START_REF] Juels | Sherlock Holmes and The Case of the Advanced Persistent Threat[END_REF][START_REF] Winder | Persistent and Evasive Attacks Uncovered[END_REF]. Much research considers that APTs are the sophisticated and target-oriented cyber attacks which often leverage customized malware and bot control techniques to remotely control the victims. [START_REF] Daly | The Advanced Persistent Threat[END_REF][2][START_REF] Hpgary | [END_REF][START_REF] Juels | Sherlock Holmes and The Case of the Advanced Persistent Threat[END_REF][START_REF] Winder | Persistent and Evasive Attacks Uncovered[END_REF]. The victims will become the stepping stones for the attackers to access valuable information inside the enterprise network [6]. Therefore, the sooner we find the APT malware-infected computers, the smaller the loss caused by the APTs.

HTTP requests log is a valuable data for determining APT malware [START_REF] Liu | N-Victims: An Approach to Determine N-Victims for APT Investigations[END_REF]. As Webrelated protocols are allowed almost everywhere, the APT malware is mostly equipped with remote-controlled ability under the HTTP-based command and control (C&C) infrastructure to facilitate the attacks on the intranet [8][START_REF] Li | Evidence of Advanced Persistent Threat: A case study of malware for political espionage[END_REF][START_REF] Liu | Retrospective Detection of Malware Attacks by Cloud Computing[END_REF]. Although much research can detect bot-infected computers [START_REF] Goebel | Rishi: identify bot contaminated hosts by IRC nickname evaluation[END_REF][START_REF] Brustoloni | Efficient Detection of Bots in Subscribers' Computers[END_REF] or detect bot behavior [START_REF] Rieck | Botzilla: detecting the "phoning home" of malicious software[END_REF][START_REF] Warmer | Detection of web based command & control channels[END_REF][START_REF] Perdisci | Behavioral clustering of HTTP-based malware and signature generation using malicious network traces[END_REF][START_REF] Gu | BotSniffer: Detecting botnet command and control channels in network traffic[END_REF], they require more bot samples to train a feasible model. This is a big problem to these approaches because the APT malware samples are few and often customized. In this paper, rather than detecting the APT malware, we take a more flexible strategy: developing a search engine for searching the potential victims to respond to APTs quickly. The working concept of our idea is shown in Fig 1. Each computer's HTTP requests are logged by proxy and sent to the search engine periodically. Once an APT malware is found, by giving the attributes of the malicious HTTP requests invoked by the APT malware, the search engine can search and rank the potential C&C servers and malware-infected computers from the historical HTTP requests. This approach is very useful for the APT investigation. We test our approach in a real APT case happened in a large enterprise network consisting of several thousands of computers, which run a commercial anti-virus system. The three known C&C servers are ranked in top 10 of the web sites. Meanwhile, in our best effort to prove, the search engine can find the other 18 C&C servers and the other 33 APT malwareinfected computers. In addition, to process the huge volume of proxy logs quickly, the search engine is implemented on Hadoop platform. In the case of 440GB HTTP logs, it can return the queries in 2 seconds.

This paper contributes to network security in the following areas:

1. Propose a rank mechanism to rank the potential APT victims and C&C servers. 2. Develop a search engine on Hadoop platform to process the huge volume of HTTP requests. 3. Prove the usefulness of our approach in a real APT investigation case. The organization of this paper is described as follows: Section 2 describes the previous research in APTs and botnet detection. In Section 3, we propose a ranking mechanism to rank the websites. Section 4 describes the prototype of the search engine. Section 5 shows experimental results. Section 6 will conclude and describe the future work.

PREVIOUS RESEARCH

APT Characteristics

As the name implies, advanced persistent threat (APT) uses highly targeted method persistently for compromising the data security, but the definition of APT in academic research is still unclear today. To understand that, we extract the APT characteristics, as shown in Table 1, described in the reports and the studies according to intrusion phases [START_REF] Larson | CCSP: Cisco Certified Security Professional Certification All-in-One Exam Guide[END_REF]. In reconnaissance phase, the targets are highly profiled including organization, people and computer environments before being attacked. The attackers do their best efforts to find out the weakness of their targets. In gaining access phase, the APT attackers use not only uncovered software vulnerabilities (zero day exploits) but also human weakness (social engineering attacks) to compromise the targets. This means that APT almost can bypass the conventional signature-based detection approaches. In maintaining access phase, the attackers often leverage bot control techniques to control the victims in the target's enterprise network. Finally, the objectives of the APT attackers are valuable information of their targets.

The research [START_REF] Thonnard | Industrial Espionage and Targeted Attacks: Understanding the Characteristics of an Escalating Threat Research in Attacks, Intrusions, and Defenses[END_REF] analyzed a large corpus of targeted attacks identified by Symantec during the year 2011. The results show that only 5% malware used in APTs were identified by antivirus software. This means that preventing the APTs in gaining access phase is very difficult, especially when the zero day exploits are used in the attacks. Once the attack success, the signature-based intrusion detection approaches are often fail because they can't recognized the malware used. For these reasons, the reaction of APTs becomes more and more important for the enterprises to reduce the damages. Therefore, we focus on the characteristics of APT in maintaining phase and give APT a definition as follows:

Table 1. The APT characteristics extracted from the studies, where phase 1 is reconnaissance, phase 2 is gaining access, phase 3 is maintaining access and phase 4 is achieve objectives.

APT is a sophisticated and target-oriented cyber attack which often leverage customized malware and bot control techniques to remotely access valuable information.

This definition indicates a key point that the APT attackers must maintain the access channels to control the victims remotely. In the cases of APT incidents, the investigations point out that these access channels are constructed by bot control techniques. The victims become the stepping stones for the attackers to access the valuable information inside the enterprise network [6]. Therefore, bot detection approaches may be applied to APT detection and investigation.

Bot Attributes and Detection

Based on the control methods, bot can be divided into several types such as IRC and HTTP bot. As web-related protocols are allowed almost everywhere, the APT malware is often equipped with remote-controlled ability under the HTTP-based C&C infrastructure to facilitate the attacks on the intranet[8, [START_REF] Li | Evidence of Advanced Persistent Threat: A case study of malware for political espionage[END_REF][START_REF] Sood | Targeted Cyber Attacks -A Superset of Advanced Persistent Threats[END_REF]. Therefore, the HTTP bot detection approaches may be useful for detecting the APT malware.

In [START_REF] Goebel | Rishi: identify bot contaminated hosts by IRC nickname evaluation[END_REF], the authors leverage the IRC nickname to detect bot contaminated hosts. They can also detect the HTTP bot by the common strings in URL of the bot servers. Based on the observation of the pre-programmed activities related to C&C, Botsniffer [START_REF] Gu | BotSniffer: Detecting botnet command and control channels in network traffic[END_REF] capture the spatial-temporal correlation in network traffic and utilize statistical algorithms to detect botnets. Botzilla [START_REF] Rieck | Botzilla: detecting the "phoning home" of malicious software[END_REF] capture malware traffic to detect the "phoning home" behavior. The phoning home traffic will be tokenized to generate the signature for detecting the malware-infected computer. In [START_REF] Perdisci | Behavioral clustering of HTTP-based malware and signature generation using malicious network traces[END_REF], the authors present a malware clustering system. They analyze the structural similarities among malicious HTTP traffic and automatically generate HTTP-based malware signatures for further detection. In [START_REF] Warmer | Detection of web based command & control channels[END_REF], the authors focus on detecting C&C channels masquerading as web traffic. They use 2v-gram based anomaly detection approach to distinguish the C&C traffic from web traffic. The summary of these studies is shown in Table 2.

Table 2 shows that the above approaches focus on detection rather than investigation. Meanwhile, except Botzilla, these approaches require a lot of malware samples to train a feasible model for detection. This is a big problem for these approaches because the APT malware samples are often few and specific. Furthermore, Botzilla leverages network level traffic for bot detection. It's almost impossible to retrospect the data for APT investigation because the size of historical network level traffic is much larger than that of application level traffic. Therefore, it is required a new approach to deal with this problem. 3 The ranking mechanism

Overview

In the enterprise network, HTTP proxy acts as an intermediary for HTTP requests from clients seeking resources from the websites. The structure of the logged HTTP requests is illustrated in Fig 2 . We leverage HTTP logs to rank the websites by the probability of being C&C servers. The probability is determined based on two observations: 1) C&C servers often contain much few information than legitimate websites. Therefore, the higher diversity of a web site is, the higher probability it is a legitimate server, and vice versa, 2) to pretend the user behavior, the malware often actively invokes HTTP requests to the C&C servers to acquire the commands for the further actions. Therefore, to rank the websites, two scores are introduced: reversed diversity score (d) and continuity score (p) of a website.

Reversed Diversity Score

Diversity score is a quantitative measure that increases when the number of types into which a set of entities has been classified increases. To estimate the diversity score of a website, the entities can be file types of the web pages. However, the logs only provide the web pages requested by the computers, not all the web pages of a website. In this case, as it looks likely the sample survey in ecology and information science, the popular diversity index Shannon-Wiener (H') [25] are used to determine the diversity score of a website. Let HTTP requests R consist of a set H of hostname, a set G of web pages, a set F of file types and a set S of source IP. Let the number of web pages and number of web pages with file type j of a website i be G i and g i,j . The diversity of the website i is calculated by Shannon-Wiener (H') as follows:

1 ' log F i j j j H f f   
, where f j = g i,j /G i .

H' value is ranged from 0 to 4.5. As the higher diversity often means higher probability of being a legitimate website, the probability (d) of a website being a C&C server is calculated by reversing the diversity:

4.5 ' 4.5 i i H d  
(2)

For the example of Table 3, the H' value and the reversed diversity score d of the three websites are:

Continuity Score

The continuity score p measures how often a website is connected by a computer. It increases when the frequency of the HTTP requests to a website increases. In this paper, we leverage the histogram approach to calculate the continuity score of a websites.

Let a period of time be L, which is divided into k bins. The count function C s (i,j) is equal to 1 if the website i appears in the HTTP requests, which is located on j bin and invoked by computer s , otherwise it is equal to 0. Let M s be the number of non-zero bins on computer s. The continuity score of website i is defined as follows:

, 1

,where = ( , )

k i s i i s j s C p C C i j M    (3)
For the example of Table 4, the timeline is divided into six parts. As the computer has no any HTTP request in t 5 , M s is equal to be 5. The continuity score of the websites is: p s,1 = (1+1+0+0+0)/5 = 0.4 p s,2 = (1+1+1+1+0)/5 = 0.8 p s,3 = (0+0+1+1+1)/5 = 0.6

Ranking the Websites

The websites are ranked by the probability of being C&C servers. The higher the Table 4. An example of calculating continuity score. reversed diversity score and continuity score of a website, the higher probability it is a C&C server. Meanwhile, the continuity score of a website is provided from the computers that have connected to it. We average them to be the final continuity score of a website. Therefore, the ranking score of a website i is defined as:

W t 1 t 2 t 3 t 4 t 5 t 6 W 1 1 1 0 0 0 0 W 2 1 1 1 1 0 0 W 3 0 0 1 1 0 1 S 1 S 2 H 1 H 2 H 3 S 3 H 4 p 1,1 p 1,3 p 3,3 p 3,4 p 2,1 p 2,2 p 2,3
, 1 ( ) / ' S i d i p s i s W w d w p S       (4)
where w d and w p are the weight of reversed diversity score and continuity score and S' is the number of the non-zero p s,i . As S 1 connects to website H 1 and H 3 , it will give the continuity score p 1,1 and p 1,3 to H 1 and H 3 individually. S 2 connects to H 1 , H 2 and H 3 , so S 2 will give three continuity scores to the three websites. Therefore, the ranking score of H 1 and H 2 will be:

1 1 1,1 2,1 ( ) / 2 d p W w d w p p      2 2 2,2 ( ) /1 d p W w d w p    

Design and Implementation

Design Overview

To realize the goal of responding to APTs quickly, two design issues are considered: 1) how to calculate the ranking score by E.q (4) quickly from the huge volume of HTTP logs (more than 30 GB per day); 2) how to extract the hit HTTP requests quickly when searching. To solving the first issue, we implement the ranking mechanism as MapReduce [START_REF] Dean | MapReduce: Simplified data processing on large clusters[END_REF] At first, the HTTP logs are duplicated, one for indexing and another for ranking. For indexing, the logs are filtered by a white list (known as legitimate website), the residual logs are indexed as the structure in Fig 2 by Lucene with the keywords "time," "ip," "method," "protocol," "hostname," "port," "path," and "type". The querying mechanism is also completed by Lucence. The user can input the query statement with the keywords to look for searching the specific HTTP requests. Meanwhile, hostname and path provides "begins with," "ends with," "contains," and "equal to" When users input a query to the system, the hostnames of the hit HTTP requests are extracted and ranked by the corresponding website's ranking score, and the system then shows the ranked results to the users.

4.2The MapReduce Jobs

The ranking scores are calculated by the MapReduce jobs. In step 1, the map function extracts hostname, path and file type from the logs to be the keys. The reduce function in step 2 sorts and removes the duplicated keys. In step 3, as the files with the same file name but located in different directory are considered different files, the reduce function makes hostname and file type as the key, and the value starts from 0 and is added by one when reducer reads a record with the same key. The final value will be the number of files with the same file types of a websites. The reduce function in step 4 calculates the reversed diversity score of the websites by E.q (2) and output the results.

In step 5, the map function extracts timestamp, source IP and hostname to be the key, where timestamp is divided by the length of bin as described in section 3.3. The reduce function in step 6 sorts and removes the duplicated keys. In step 7, the reduce function ignores the hostname and makes timestamp and source IP as key to count the number of non-zero size bins M s . Step 8 is another branch from step 6, it makes source IP and hostname as the key and calculates C i . Step 9 refers to the outputs of step 7 and step 8 to calculate the continuity score of a website by E.q (3). Finally, step 10 calculates the ranking score by E.q (4) based on the results of step 4 and step 9.

Experiments and Evaluation

The Experiments Setup

To evaluate the effectiveness of our approach, we collected the proxy logs of the enterprise network consisting of several thousands of computers for two weeks, from October 11 to October 24, 2011, as the experimental data. The attributes of the experimental data are shown in Table 5. The experimental data consists of three C&C servers and the HTTP requests of five malware-infected computers which were found in December 14, 2011. Two reasons make us believe this is an APT attack: 1)the computer is a stepping stone and the footprints can be traced back to 8 months ago and 2)the malware has the similar abilities, such as remote access, key logger, packet forward, DLL injection and so on, as described in [START_REF] Daly | The Advanced Persistent Threat[END_REF]6,8,29]. Meanwhile, as we don't know how many computers were infected actually in the data, in our best effort, we investigate all potential victims detected by our approach manually. The investigations are used for evaluating the accuracy of the search engine.

Finally, the performance of the search engine is a key point in this study. Five servers, one for the Hadoop master and four for the slaves, ran on CentOS 5.4 with a 2.26 GHz Intel Xeon CPU and 12 GB RAM. The version of Hadoop used was 1.0.1 and that of Lucene was 3.5. The log files for two weeks were fed to our system to evaluate the performance of indexes building, ranking scores calculation and query.

Determine the weights

The weight w d and w p in E.q(4) should be determined at first. We select the first week's logs to observe the reversed score and continuity score of the websites. We set L to be one week and k to be 1 hour. Fig 6 depicts the distribution of the reversed diversity score and continuity score. Over 70% website's reversed diversity score is between 1~0.9. This is because 1) proxy servers can't log the details of HTTPS requests, the reversed diversity scores of all the HTTPS websites are equal to 1 and 2) some websites are connected for only a few times, so their reversed diversity scores are also equal to 1.Therefore, we ignored the HTTPS websites and the lower traffic websites (less than 10 HTTP requests).

The continuity score of most websites is lower than 0.1 (over 94%). The continuity score of the known C&C servers is between 0.8~1.0. However, the number of the websites with continuity score between 0.9 and 1.0 is larger than that of the websites with continuity score between 0.8 and 0.9. It is because some websites are connected by a few clients and their IP also only connect to these websites. To deal with this problem, we remove the continuity score which is given from the source IPs with M s <12, which means that in the two weeks the hours that a computer invoked HTTP requests are less than 12. Finally, as the impact of continuity score is larger than reversed diversity score, we set w d to be 0.2 and w p 0.8 in the further experiments.

Experiment Results

To evaluation the accuracy of the search engine, the experimental data is fed to the search engine. We set L to be two weeks and k to be one hour. The known malicious HTTP request r m :=<m=GET, p=http, n=443, l=/FC001/xxx, e=-> invoked by APT malware are the references of the queries. To form the queries, we fix method, protocol and port and give three statements, where Q 1 = path contains "FC001", Q 2 = type is equal to "-" and Q 3 = any path and type. The ranking results in Table 6 show that the search engine can find the three known C&C servers by Q 1 . Meanwhile, it also finds the other 6 unknown C&C servers. According to the found C&C servers, we find the other 11 potential victims which are real victims proved by investigations.

The search engine returns more websites by Q 2 . Since the precise rate of being C&C server in top 20 websites is lower than the results by Q 1 , Q 2 finds the other four C&C servers. The legitimate websites in top 20 are consisted of three types: web game, availability test of a website and flash video. In the test of Q 3 , the search engine returns more websites than Q 1 and Q 2 . Notably, the precise rate in top 20 websites of Q 3 is higher than that of Q 2 . Meanwhile, the other five C&C servers are found by Q 3 . This is because a new APT malware invokes the HTTP request r' m :=<GET, http, 443, /90ad.asp, asp>, which is unknown before the experiments. For further investigation, 33 of 38 potential victims are proved being infected by the unknown malware.

In performance evaluation, the results in Table 7 show that the execution time of building index and calculating ranking score is more than 21 hours. This doesn't include the time for uploading log files to the servers. On average, the daily logs can be processed in 3.5 hours. We also test the system responding time by above three queries. The results show that the three queries can be completed in 2 second. The execution time of Q 2 and Q 3 are longer than that of Q 1 . This is because the more websites hit, the more time the search engine requires to display them.

Conclusion

This paper develops a search engine on Hadoop platform to search potential C&C servers and victims for APT investigation. In the real APT investigation, we prove that the search engine can rank the known C&C servers in top 10 websites. The search engine also finds out the other C&C servers and potential victims. Meanwhile, the responding time of each query is less than 2 second. The future work may include: 1) if the malware communicates with the C&C server through HTTPS, our approach may fail to find them. The statistical-based approaches may be a chance to improve the ranking mechanism; 2) the fast flux botnet changes the domain name frequently, so the websites may be ignored because of fewer HTTP requests. The ranking mechanism may be improved by introducing other supplemental attributes, such as TTL value or domain name location.

Fig 1 :

 1 Fig 1: The working concept of the search engine.

H' 1 =

 1 -(0.99/(log0.99) + 0.01(log0.01)) = 0.056 d 1 = (4.5-0.056)/4.5 = 0.987 H' 2 =-(0.5/(log0.5) + 0.5(log0.5)) = 0.693 d 2 = (4.5-0.693)/4.5 = 0.846 H' 3 =-(0.33/(log0.33)+0.33/(log0.33)+0.33/(log0.33))= 1.1 d 3 = (4.5-1.1)/4.5 = 0.755

d 1 d 2 d 3 d 4 Fig 3 .

 43 Fig 3. Example of HTTP requests.

Fig 3

 3 is an example of HTTP requests, three source IP S 1 , S 2 and S 3 connect to websites H 1 , H 2 , H 3 and H 4 , each of which reversed diversity score is d 1 , d 2 , d 3 , and d 4 .

Fig 4 .

 4 Fig 4. High level working architecture operators, the other keywords only provide an "equal to" operator.When users input a query to the system, the hostnames of the hit HTTP requests are extracted and ranked by the corresponding website's ranking score, and the system then shows the ranked results to the users.

Fig 6 .

 6 Fig 6. The distribution of the reversed diversity score and continuity score.

Table 2 .

 2 The summary of HTTP bot detection approaches.

	Item	[11]	[16]	[13]	[15]	[14]
	Objective	Bot	Bot	Bot	Bot	C&C
		detection	detection	detection	detection	detection
	Traffic level	Application Application Network	Application Application
	Match function	RE	NG	NG	NG or RE	NG
	Require many-	Yes	Yes	No	Yes	Yes
	malware samples
					RE: Regular Expression NG: N-Gram

  HTTP log structure, where t is the timestamp, s is source IP, m is method, h is hostname, p is protocol, n is port, l is path and e is web page's file type.

	2012-01-01 01:01:01 10.52.9.229 GET http ad1.nownews.com 80 /ad/include/ads.php php
	t	s	m	p	h	n	l	e
	Fig 2.

Table 3 :

 3 An example of three websites that have three file types and the number of corresponding files.

	Website	HTML	ASP	JPG
	W 1	99	1	0
	W 2	50	50	0
	W 3	33	33	33

  jobs on Hadoop platform [27]. The second issue is solved by Lucene [28]. The high level working architecture of the system is shown in Fig 4.

Table 5 .

 5 The attributes of the experimental data

	Data Size	Source IP	Hostname	HTTP requests
	440GB	19,633	267,962	273,195,451

Table 6 .

 6 The ranking results of the three queries

	Queries

Table 7 .

 7 The performance of the search engine.

	MapReduce job	Execution Time
	Building index	21 hours
	Calculating ranking score	27 hours
	Querying by Q 1	< 0.6 second
	Querying by Q 2	< 1.6 second
	Querying by Q 3	< 2 second

Acknowledgments.

The authors would like to thank reviewers' helpful comments. This research is partially supported by the Information & Communication Security Lab, Telecommunication Laboratories, Chunghwa Telecom co., Ltd, the National Science Council of Taiwan, ROC under Grant No. NSC101-2218-E-008-004.