Abstract:The logic relationship among equality and inequality constraints in a standard constrained optimization problem (SCOP) is only logic AND, however in a generalized constrained optimization problem (GCOP) it contains not only logic AND but also logic OR.GCOP is also known as disjunctive programming problem.The rate-monotonic (RM) optimal problem is an important instance of GCOP.Existing methods for the RM optimal problem include function transformation, mixed integer programming and linear programing search.But all these methods are not efficient enough with the increase of task volume.A linear programming based hybrid search (LPHS) method is proposed in this paper.First GCOP problem is partitioned into linear problemming sub-problems, and a linear search tree is constructed.Next, this tree is searched by the strategy of mixing depth-first-search and breadth-first-search, and an efficient pruning method is used during search progress.Then, the optimal solution is achieved.Experimental results illustrate that LPHS method is much more efficient than others.This work is related to satisfiability modulo therories (SMT), and is expected to improve the efficiency of SMT solvers and to promote applications of SMT in software verification, symbolic excecution and other fields.

Abstract:Bosbach states and Riečan states are two different types of many-valued generalizations of classical probability measures on Boolean algebras by extending the prominent Kolmogorov axioms in different ways.Being regarded as algebraic and axiomatic counterparts of the semantic quantification in probabilistically quantitative logic, both states draw great interests of researchers in the community of non-classical mathematical logics.It has been proved in the literature that Bosbach states and Riečan states coincide on many-valued logical algebras having the Glivenko property, and that the Glivenko property plays a key role in the study of construction and existence of states on logical algebras.This paper studies the Glivenko property of NMG-algebras with respect to a nucleus, providing several necessary and sufficient conditions for the underlying nucleus to be a homomorphism into the NMG-algebra with its range as the supporting set.A particularly interesting characterization shows that a nucleus on an NMG-algebra is such a homomorphism if and only if it is a double relative negation defined by an involutive element whose (canonical) negation is a fixpoint of the t-norm square operation.

Abstract:In software product lines, the core of product customization is to select appropriate features.Due to the various competing and even conflicting non-functional requirements (NFRs), feature selection, in essential, is a multi-objective optimization process.What's more, the search space in optimization is constrained largely by the relationships between features and the definitive functional requirements (FRs).Besides, some NFRs are with clear numerical limits, while others are not.These varied types of NFRs also present challenges for feature selection.To solve these problems, a novel multi-objective optimization algorithm with a feature selection reviser is proposed.Firstly, description language for the dependency and constraints relationships between features (DL-DCF) are designed to format different types of relationships between features uniformly, which stipulates the coexistence of two or more features.Next, during selection, all NFRs are transformed to optimization goals, and the quantified constraints on NFRs are used as filters to exclude invalid solutions.Furthermore, a reviser is designed to repair the configuration which violates any relation between features or FRs.Finally, the reviser is planted into the multi-objective optimization framework to form the proposed algorithm, MOOFs, to perform feature selection.Comparing with four popular baselines running on four feature models with different scales, empirical results show notable performance improvement of the algorithm on efficiency of valid solution generation and on the multiple NFRs balancing, especially when the feature models are large and complex.

Abstract:The generated system state space can be very large when a complex software system is tested.In order to avoid the unnecessary traversing of the entire state space, a new method is presented based on the combination of CPN modeling and on-the-fly method to generate test cases.During such a process, only part of the state space is traversed according to the tester's personnel interest.Firstly, both the definitions of CPN and the extended reachability graph are introduced, and the related concepts relating to the on-the-fly testing method, including system specification, test purpose, synchronous product and test cases, are introduced.Secondly, a synchronous product algorithm is implemented, and the test cases are designed to test the algorithm as well.Finally, an implementation under test is selected to sample the combination method of CPN modeling and on-the-fly method.The interactions between the tester and the implementation under test are realized through an adapter, and the test cases are generated and executed simultaneously.Thus the feasibility and the effectiveness of the proposed method are verified.

Abstract:Return-Oriented programming (ROP) is widely applied in modern software vulnerability exploitations.This work demonstrates that Turing-complete ROP code is universally available in everyday software.A big challenge for applying ROP is to construct the functionality of conditional jumps.Because conditional branch instructions are abandoned as they are deemed no use for achieving this functionality, existing works resort to some awkward methods which suffer from high risk of failure.By analyzing the execution context of conditional branch instructions, this study finds that the traditional viewpoint on these instructions only partially reveals the truth.In fact, there are some conditional branch instructions in which two branches each starts a reusable gadget, and these two gadgets fetch the next gadget from different memory cells.Hence, the code snippets beginning at these conditional instructions can implement the conditional jumps for ROP code.Such a code snippet is named if-gadget.Experimental results show that if-gadgets are widely available in executables of Linux and Windows platforms.Evaluations on programs of Binutils demonstrate that, Turing complete ROP code can be achieved with the help of if-gadgets while existing techniques even fail to gather Turing complete gadgets.On platforms such as Ubuntu, because the executables running on them do not support ASLR by default, attackers can construct Turing-complete ROP code on these executables and then mount an attack.Therefore, ROP-based attacks pose a great threat to modern platforms, which is far more serious than originally thought.

Abstract:Extreme learning machine (ELM) not only is an effective classifier in supervised learning, but also can be applied on semi-supervised learning.However, semi-supervised ELM (SS-ELM) is merely a surface learning algorithm similar to Laplacian smooth twin support vector machine (Lap-STSVM).Deep learning has the advantage of approximating the complicated function and alleviating the optimization difficulty associated with deep models.Multi layer extreme learning machine (ML-ELM) has been developed according to the idea of deep learning and extreme learning machine, which stacks extreme learning machines, based auto encoder (ELM-AE) to create a multi-layer neural network.ML-ELM not only approximates the complicated function but also avoids the need to iterate during training process, exhibiting the merits of high learning efficiency.In this article, manifold regularization is introduced into the model of ML-ELM and a Laplacian ML-ELM (Lap-ML-ELM) is put forward.Furthermore, in order to solve the over fitting problem with ELM-AE, weight uncertainty is brought into ELM-AE to form a weight uncertainty ELM-AE (WU-ELM-AE) which can learn more robust features.Finally, a weight uncertainty Laplacian ML-ELM (WUL-ML-ELM) is proposed based on the above two algorithms, which stacks WU-ELM-AE to create a deep network and uses the manifold regularization framework to obtain the output weights.Lap-ML-ELM and WUL-ML-ELM are more efficient than SS-ELM in classification and do not need to spend too much time.Experimental results show that Lap-ML-ELM and WUL-ML-ELM are efficient semi-supervised learning algorithms.

Abstract:Tagging has become one of the most significant methods for information organization.With the proliferation of recommending systems, tag recommendation problem has attracted more and more attention from researchers.Currently, while a variety of tagging systems exist, as the system function becomes more and more complex, the information of tagging data generated by tagging system becomes increasingly complex.In this paper, a tagging system is modeled as a heterogeneous network.To learn the importance of different types of nodes and edges, a general graph-based model, called HnMTR, is proposed.First, HnMTR maps different heterogeneous objects into a unified space so that objects from different dimensions can be directly compared.Then multivariate Markov model is applied to the mapped network to rank tag nodes.Highly ranked tags are recommended for the user.Experiments on three real world datasets with different tagging behavior demonstrate that the proposed method outperforms the state-of-the-art methods significantly.

Abstract:Anomaly detection is an important research area of data mining.Current outlier mining approaches based on the distance or the nearest neighbor can result in unmanageable long operation time when applied to massive high-dimensional data.Many improvements have been proposed to improve the algorithms, but the detection is ineffective.This paper presents a new anomaly detection algorithm based on the local distance of density-based sampling data.First, the density-based of probability sampling method is used to find a subset of the data in detection.Then, the method based on the local distance of local outlier detection is used to calculate the abnormal factor of each object in the subset.In using the density-based of sample data, the abnormal factor is obtained both as local outlier factor of the subset and as the approximate value of global outlier factor of the hole data.Having the abnormal factor of each object in the subset, data points with higher factor score indicate higher degree of outliers.Experimental results show that, compared with the existing algorithms, this algorithm has higher detection accuracy and less computation time.The algorithm has higher efficiency and stronger scalability for various dimensions and size of data points.

Abstract:The development of next-generation high-throughput DNA sequencing techniques has greatly promoted the research of structural variations (SVs) detection.Current genetic structure variation detection methods are mainly base on depth of coverage, pair-end mapping clusters, or sequence assembly, some of them are known to be not accurate or too sensitive.What's more, some methods are not able to recognize the specific position and sequence of structural variation.Insertions and deletions (indels) are the most common forms of genome structure variations.This paper puts forward an optimal split-read matching algorithm (OSRM) using dynamic programming.OSRM breaks an abnormal read into several reads in a least quantity.First, a score matrix of the abnormal read and the corresponding referenced sequence is created.Then a matrix of backtracking path is established.Next, a formula designed according to the characteristics of structural variation is used to elect the optimal backtracking path matrix.And finally the split-read and referenced sequence are matched in an optimal arrangement by which the accurate position and sequence of found indels are outputted.Experiments prove that the performance of algorithm is excellent.In addition, compared with Pindel which is the best in split-read methods, OSRM can offset its defection in detecting small and medium indels while also be able to detect more complex situation.

Abstract:Temporal Twitter summarization is an important sub-task of text summarization, which aims to extract a concise tweet set with time, goes from a huge Twitter stream.It helps users quickly understand a specific event.As one of the most popular social media platforms, the explosive growth of Twitter information makes it difficult for users to find reliable and useful information.As tweets are short and highly unstructured, it makes traditional document summarization methods difficult to handle Twitter data.Meanwhile, Twitter also provides rich temporal-social context more than texts, bringing new opportunities.This paper considers Twitter stream as a kind of signal, and proposes a novel temporal Twitter summarization method by modeling macro-micro temporal context and social context through analyzing the complex noises hidden in signal.First, time points of hot sub-events are detected by modeling temporal context globally with wavelet analysis.Second, a novel random walk model is built on graph based unsupervised Twitter summarization framework, integrating both local temporal context and social user authority to generate summary for each sub-event time point.To evaluate the proposed framework, a real-world Twitter dataset, including expert time point and summary, is manually labeled.Experimental results show that wavelet analysis during hot sub-event time point detection and temporal-social context in Twitter summarization are both effective.

Abstract:Aggregation task for Chinese short texts is to associate a pair of similar short texts together.The pair needs to belong to same entity in two data sets.Such study has important theoretical and practical interests for data resource integration across different fields.In this article, an effective aggregation model is devised for Chinese short text.The model is able to decrease the volume of candidate pairs sharply for matching and ensure the matching accuracy via two key steps, namely fast matching and refined matching.Meanwhile, aiming to the deficiency of the traditional similarity algorithms for short text, an improved similarity algorithm, called generalized Jaro-Winkler is proposed.The aggregation experiments performed on different merchant data sets suggest that the new algorithm has the best performance both in matching accuracy and stability compared with those traditional algorithms.

Abstract:The social network is complicated with different evolution mechanisms.It is of great significance to reasonably analyze social network evolutions and effectively detect social events.The event detection methods based on link prediction make most of the limited network topological information, discover the network evolution fluctuation, and detect events.However, most of existing methods are limited by the assessment measures of link prediction, and neglect the otherness of micro node evolution mechanisms.They use the same similarity index to describe evolution fluctuations of different nodes, which is adverse to the performance of event detection.To improve the accuracy and sensitivity of event detection, this paper proposes an event detection method based on node evolution fluctuation for social networks (NodeED).The method consists of a node similarity index judgement algorithm (SimJudge) and a micro evolution fluctuation detection algorithm (MicroFluc).The main work is as follow: (1) Based on the particle swarm algorithm, SimJudge is proposed to compare the description performances of different similarity indexes for a node evolution fluctuation.Different nodes can find their optimal similarity indexes at different periods by SimJudge; (2) To quantify the effect of events, MicroFluc is proposed to consider the diversity of node evolution fluctuations and evaluate the entire network evolution fluctuation; (3) In real social networks VAST and ENRON, NodeED results in the event detection sensibility increase by 100% in VAST and 50% in ENRON, which shows NodeED has more advantages to detect events in social networks than other methods.

Abstract:The preference-based multi-objective evolutionary algorithms are the sort of evolutionary algorithms to assist the decision maker (DM) in finding interesting Pareto optimal solutions.At present, the inappropriate locations of the reference points sometimes seriously impact the convergence performance of the algorithms when the locations of the reference points are used as the preference information during the optimization.Moreover, the size of the preferred region is difficult to control.And the comprehensive performance of the algorithms will degrade in dealing with many-objective problems.To address the above issues, in this paper, the self-adjustable preference-based radius is calculated to build a new preference relation model, and by dividing region of interest (ROI), a preference-based multi-objective evolutionary algorithm based on the division of RoI is proposed.The proposed algorithm is compared with four reference point based multi-objective evolutionary algorithms (g-NSGA-II, r-NSGA-II, angle-based preference algorithm and MOEA/D-PRE).The results show that the proposed algorithm has good convergence and diversity, and at meantime allows the DM control the size of the preferred region.In addition it has a good convergence in addressing the many-objective problems.

Abstract:In many applications, when a user needs to access sensitive information, it is a usual requirement to authenticate whether or not the user satisfies certain processes.Existing encryption schemes are not applicable for this scenario.To adderess this problem, a new cryptography primitive called process pased encryption (PBE) is presented.The application scenario of PBE is demonstrated.PBE is classified into two categories: Key policy process based encryption (KP-PBE) and ciphertext policy process based encryption (CP-PBE).A KP-PBE scheme is constructed utilizing the tools of bilinear map and linear secret sharing scheme (LSSS).Compared to conventional attribute based Eecryption (ABE), the performance of KP-PBE is much better on describing processes.Finally, the security of KP-PBE is proven under the selective security model.

Abstract:The mixed denial-of-service attacks have become the mainstream threat to the Internet service availability.Tracing an individual attack packet to its origin is an important step in defending against such attacks.For this reason, researchers have proposed several approaches for single-packet IP traceback.However, these prior works suffer from the following disadvantages: The high process overhead at routers and low traceback accuracy.To address the issue, this paper proposes an efficient and precise approach, termed as S3T, for single-packet traceback based on label switching.Borrowing the idea of label switching principle in MPLS networks, its main method is to make use of the reverse routing to set up audit trails, and then employ parallel processing of audit trail establishment, more flexible storage assignment for traceback routers and adaptive adjustment for the audit trail retention time to overcome those drawbacks.Extensive analysis and simulation are carried out to conduct thorough numerical comparisons between S3T and the state-of-the-art approaches.The results show that S3T significantly outperforms the existing approaches in terms of the process overhead at routers, as well as the traceback accuracy.

Abstract:Certificateless signcryption is a useful cryptographic primitive which simultaneously provides the functionalities of certificateless encryption and certificateless signature.In the past few years, some certificateless signcryption schemes have been proposed, and claimed to be provably secure.Unfortunately, concrete attacks can be made that indicate that some existing certificateless signcryption schemes are not secure.To overcome these disadvantages, an efficient certificateless signcryption scheme without bilinear pairings is proposed.The proposal is provably secure in the random oracle model based on the computational Diffie-Hellman problem and discrete logarithm problem, and also has the security properties such as non-repudiation and public verifiability.Additionally, compared with other existing certificateless signcryption schemes in the computational complexity, the proposed method is more efficient and secure due to the lack of bilinear pairings.

Abstract:The robustness of complex network against cascading failures is of great significance.Based on the weighted scale-free network, a new cascading failure model with adjustable parameters is proposed.In this model, the nodes' initial loads are constructed with node betweenness, node degree, node weight and neighbor node's weight from both global and local perspective.Meanwhile, the initial load is made proportional to the node capacity.Adopting a new redistribution rule, the failed nodes' loads are assigned to their neighbors.Then the load parameters can be obtained through analyzing the cascade failure process.Finally, the effectiveness of the proposed method are verified by experiment.

Abstract:The integration of trusted computing into virtual computing system can enable the hardware-based protection of trustworthiness in application areas such as cloud computing and network function virtualization (NFV).In a physical trusted platform module (pTPM) based virtual trusted platform module (vTPM), each virtual machine (VM) can be viewed as having its own private TPM.However, it is necessary to extend the trustworthiness of pTPM to vTPM so that a challenger can believe the vTPM is the root of trust of the VM.The existing techniques mainly use a certificate chain to build a trust link from pTPM to vTPM.But if these techniques were deployed in the scenario with frequent vTPM migrations, there would be very high cost of reacquiring new certificates for the migrated vTPM, moreover, pTPM couldn't revoke its trust extension in real time, and they couldn't provide forward security.This paper presents an approach of vTPM dynamic trust extension (DTE) to satisfy the requirements of frequent migrations.With DTE, vTPM is a delegation of the capability of signing attestation data from the underlying pTPM, with one valid time token issued by an authentication server (AS).DTE maintains a strong association between vTPM and its underlying pTPM, and has clear distinguishability between vTPM and pTPM because of the different security strength of the two types of TPM.In DTE, there is no need for vTPM to re-acquire identity key (IK) certificate(s) after migration, and pTPM can have a trust revocation in real time.Furthermore, DTE can provide forward security.Performance measurements and analysis of its prototype demonstrate that DTE is feasible.

Abstract:Comparing with the classical level set, the variational level set without re-initialization can avoid repeating initialization, which greatly reduces the algorithm's running time while using the edge gradient information of images to accurately capture the local structure.However, this model cannot adaptively obtain initial curve, and the model's topology cannot be changed to detect multiple targets.To solve the problems above, this paper proposes an adaptive contour based variational level set model for multiple target detection in complex background.First, the inter-frame difference algorithm is combined with K-means clustering algorithm to obtain multiple initialization curves, and then the noise is reduced by morphology method.This can estimate the position and the size of the moving target in complex background.The variational level set without re-initialization is further extended to multiple targets from single target, and the model's ability is improved to deal with the images of non-uniform gray.Experiments on standard database and real scene data sets indicate that the proposed method can accurately locate targets contours of different scales and gray to improve the evolution efficiency and accuracy of the algorithm.