Blind image quality assessment (BIQA) methods often incorporate auxiliary tasks to improve performance. However, existing approaches face limitations due to insufficient integration and a lack of flexible uncertainty estimation, leading to suboptimal performance. To address these challenges, we propose a multitasks-based Deep Evidential Fusion Network (DEFNet) for BIQA, which performs multitask optimization with the assistance of scene and distortion type classification tasks. To achieve a more robust and reliable representation, we design a novel trustworthy information fusion strategy. It first combines diverse features and patterns across sub-regions to enhance information richness, and then performs local-global information fusion by balancing fine-grained details with coarse-grained context. Moreover, DEFNet exploits advanced uncertainty estimation technique inspired by evidential learning with the help of normal-inverse gamma distribution mixture. Extensive experiments on both synthetic and authentic distortion datasets demonstrate the effectiveness and robustness of the proposed framework. Additional evaluation and analysis are carried out to highlight its strong generalization capability and adaptability to previously unseen scenarios.

Recent advances in multimodal large language models (MLLMs) have significantly improved medical AI, enabling it to unify the understanding of visual and textual information. However, as medical knowledge continues to evolve, it is critical to allow these models to efficiently update outdated or incorrect information without retraining from scratch. Although textual knowledge editing has been widely studied, there is still a lack of systematic benchmarks for multimodal medical knowledge editing involving image and text modalities. To fill this gap, we present MedMKEB, the first comprehensive benchmark designed to evaluate the reliability, generality, locality, portability, and robustness of knowledge editing in medical multimodal large language models. MedMKEB is built on a high-quality medical visual question-answering dataset and enriched with carefully constructed editing tasks, including counterfactual correction, semantic generalization, knowledge transfer, and adversarial robustness. We incorporate human expert validation to ensure the accuracy and reliability of the benchmark. Extensive experiments on state-of-the-art general and medical MLLMs demonstrate the limitations of existing knowledge editing methods in the medical domain, highlighting the need to develop specialized editing strategies.

Molecular assembly (MA) has long been a fundamental task in chemistry and biology, with the potential to create new materials and enable novel functions beyond the molecular scale. However, its vast conformational search space poses substantial challenges, and current generative models remain limited in capturing molecular flexibility and preventing non-physical poses. In this paper, we propose AssemUDB, a diffusion bridge–based framework that learns transport mappings between two distinct flexible domains for molecular assembly generation. We reformulate the marginal matching constraint of diffusion bridges as a coupling distribution governed by unbalanced transport rather than imposing strict conservation. Subsequently, we employ a progressive process from structural relaxation in Euclidean space to assembly on the SE(3) manifold. This relaxation of marginal conservation grants the generative model greater flexibility and leads to more physically plausible atom placements. Comprehensive experiments demonstrate the superior performance of AssemUDB. Notably, we find that the method demonstrates performance comparable to, or even better than, mature tools such as PackMol for packing tasks.

Recent advancements in Multimodal Large Language Models (MLLMs) have demonstrated impressive capabilities in interpreting single medical images. However, real-world clinical diagnosis is intrinsically a multi-view process, requiring the synthesis of information across volumetric slices, temporal sequences, and comparative modalities. Existing benchmarks fail to capture this complexity, limiting the assessment of models in realistic clinical workflows. To bridge this gap, we introduce MedMultiBench, the first large-scale benchmark specifically designed for medical multi-image understanding. Comprising 11,392 expert-curated samples, MedMultiBench evaluates MLLMs across four distinct dimensions: Joint Reasoning, Comparative Analysis, Comprehensive Perception, and In-Context Learning. We benchmark 13 state-of-the-art MLLMs, revealing that while current models excel in single-view tasks, they struggle significantly with multi-image contexts. Our experiments identify a performance degradation in open-source models when processing increased visual loads, whereas closed-source models demonstrate better scalability. MedMultiBench provides a robust framework to facilitate the development of MLLMs capable of holistic clinical reasoning.

Coarse-grained (CG) molecular dynamics of proteins is a preferred approach to studying large molecules on extended time scales by condensing the entire atomic model into a limited number of pseudo-atoms and preserving the thermodynamic properties of the system. However, the significantly increased efficiency impedes the analysis of substantial physicochemical information, since high-resolution atomic details are sacrificed to accelerate simulation. In this paper, we propose LatCPB, a generative approach based on diffusion that enables high-resolution backmapping of CG proteins. Specifically, our model encodes an all-atom into discrete latent embeddings, aligned with learnable multimodal discrete priors for circumventing posterior collapse and maintaining the discrete properties of the protein sequence. During the generation, we further design a latent diffusion process within the continuous latent space due to the potential stochastics in the data. Moreover, LatCPB performs a contrastive learning strategy in latent space to separate feature representations of various molecules and conformations of the same molecule, thus enhancing the comprehension of molecular representational diversity. Experimental results demonstrate that LatCPB is able to backmap CG proteins effectively and achieve outstanding performance.

Currently, medical vision language models are widely used in medical vision question answering tasks. However, existing models are confronted with two issues: for input, the model only relies on text instructions and lacks direct understanding of visual clues in the image; for output, the model only gives text answers and lacks connection with key areas in the image. To address these issues, we propose a unified medical vision language model MIMO, with visual referring Multimodal Input and pixel grounding Multimodal Output. MIMO can not only combine visual clues and textual instructions to understand complex medical images and semantics, but can also ground medical terminologies in textual output within the image. To overcome the scarcity of relevant data in the medical field, we propose MIMOSeg, a comprehensive medical multimodal dataset including 895K samples. MIMOSeg is constructed from four different perspectives, covering basic instruction following and complex question answering with multimodal input and multimodal output. We conduct experiments on several downstream medical multimodal tasks. Extensive experimental results verify that MIMO can uniquely combine visual referring and pixel grounding capabilities, which are not available in previous models. Our project can be found in https://github.com/pkusixspace/MIMO.

Rule learning-based models are widely used in highly interpretable scenarios due to their transparent structures. Inductive logic programming (ILP), a form of machine learning, induces rules from facts while maintaining interpretability. Differentiable ILP models enhance this process by leveraging neural networks to improve robustness and scalability. However, most differentiable ILP methods rely on symbolic datasets, facing challenges when learning directly from raw data. Specifically, they struggle with explicit label leakage: The inability to map continuous inputs to symbolic variables without explicit supervision of input feature labels. In this work, we address this issue by integrating a self-supervised differentiable clustering model with a novel differentiable ILP model, enabling rule learning from raw data without explicit label leakage. The learned rules effectively describe raw data through its features. We demonstrate that our method intuitively and precisely learns generalized rules from time series and image data.

Medical Visual Question Answering (Medical VQA) plays an important role in medical informatics. However, the robustness of existing medical VQA models is severely challenged by adversarial attacks. Current methods (e.g. adversarial training and noise-based reasoning) heavily rely on additional data or complex procedures and often ignore model-level robustness. To address these issues, we propose Multimodal Variational Masked Autoencoder (MVMAE), a novel pre-training framework designed to enhance the robustness of the medical VQA task. MVMAE leverages masked modeling and variational inference to extract robust multimodal features. The framework introduces a low-cost multimodal bottleneck fusion module and employs reparameterization to sample robust latent representations, ensuring effective feature fusion and reconstruction. Extensive experiments on public medical VQA datasets demonstrate that MVMAE significantly improves resistance to various adversarial attacks and outperforms other medical multimodal pre-training methods.

Molecular synthetic space projecting is a critical technique in de novo molecular design, which aims to rectify molecules without synthesizability guarantee by converting them into synthetic postfix notations. However, the vast synthesizable chemical space and the discrete data modalities involved pose significant challenges to postfix notation conversion benchmarking. In this paper, we exploit conditional probability transitions in discrete state space and introduce MoleBridge, a deep generative model built on the Markov bridge approach for designing postfix notations of molecular synthesis pathways. MoleBridge consists of two iterative optimizations: i) Autoregressive extending of notation tokens from molecular graphs, and ii) generation of discrete reaction postfix notations through Markov bridge, where noisy token blocks are progressively denoised over multi-step iterations. For the challenging second iteration, which demands sensitivity to incorrect generative probability paths within intricate chemical spaces, we employ a thinking and denoising separation approach to denoise. Empirically, we find that MoleBridge is capable of accurately predicting synthesis pathways while exhibiting excellent performance in a variety of application scenarios.

In this paper, we investigate tradeoffs among differential privacy (DP) and several important voting axioms: Pareto efficiency, SD-efficiency, PC-efficiency, Condorcet criterion, and Condorcet loser criterion. We provide upper and lower bounds on the two-way tradeoffs between DP and each axiom. We also provide upper and lower bounds on three-way tradeoffs among DP and every pairwise combination of all the axioms, showing that, while the axioms are compatible without DP, their upper bounds cannot be achieved simultaneously under DP. Our results illustrate the effect of DP on the satisfaction and compatibility of voting axioms.

As a distributed machine learning paradigm, vertical federated learning enables multiple passive parties with distinct features and an active party with labels to train a model collaboratively. Although it has been widely applied for its ability to protect privacy to some extent, this paradigm still faces various threats, especially the label inference attack (LIA). In this paper, we present the first observation of the disparity in LIAs resulting from differences in feature distribution among passive parties. To substantiate this, we study four different types of LIAs across five benchmark datasets, investigating the potential influencing factors and their combined impact. The results show that attack performance disparities can vary up to 15 times among different passive parties. So, how to eliminate this disparity? We explore methods from both attack and defense perspectives, including learning rate adjustment and noise perturbation with differential privacy. Our findings indicate that a modest increase in the learning rate of the passive party effectively enhances the LIA performance. In light of these, we propose a novel defense strategy that identifies passive parties with important features and applies adaptive noise to their gradients. Experiments show that it effectively reduces both attack disparity among passive parties and overall attack accuracy, while maintaining low computational complexity and avoiding additional communication overhead. Our code is publicly accessible athttps://github.com/WWlnZSBMaXU/Attackers-Are-Not-the-Same.

Complementarity determining region (CDR) is a specific region in antibody molecules that binds to antigens, where a small portion of residues undergoes particularly pronounced variations. Generating CDRs with high affinity and specificity is a pivotal milestone in accelerating drug development for daunting and unresolved diseases. However, existing approaches predominantly center on characterizing the attributes of residues through sequential generation models, thus falling short in effectively modeling the intricate spatial correlations among residues and frequently succumbing to the trap of generating sequences that exhibit a high degree of arbitrariness. In this article, we propose a novel synergistic attention-guided cascaded graph diffusion model, termed GraphCas, which offers a pathway for optimized generation of high-affinity CDRs. Our approach is the first cascaded-based graph diffusion model for CDR synthesis. Specifically, we design a graph propagation algorithm with a relation-aware synergistic attention mechanism, enabling the targeted acquisition of structural insights from diverse protein sequences and bolstering the global information representation of the graph by precisely localizing to long-range key residue sites. We design a cascaded conditional enhanced diffusion approach, providing the capability to incorporate additional control constraints into the input. Experimental results demonstrate that GraphCas can generate photo-realistic CDRs and achieve performance comparable to top-tier approaches. In particular, GraphCas reduces the RMSD by nearly 0.42 units in the H1 region and improves the ERRAT by 9.36% points in the L1 region.

The actual collection of tabular data for sharing involves confidentiality and privacy constraints, leaving the potential risks of machine learning for interventional data analysis unsafely averted. Synthetic data has emerged recently as a privacy-protecting solution to address this challenge. However, existing approaches regard discrete and continuous modal features as separate entities, thus falling short in properly capturing their inherent correlations. In this paper, we propose a novel contrastive learning guided Gaussian Transformer autoencoder, termed GTCoder, to synthesize photo-realistic multimodal tabular data for scientific research. Our approach introduces a transformer-based fusion module that seamlessly integrates multimodal features, permitting for mining more informative latent representations. The attention within the fusion module directs the integrated output features to focus on critical components that facilitate the task of generating latent embeddings. Moreover, we formulate a contrastive learning strategy to implicitly constrain the embeddings from discrete features in the latent feature space by encouraging the similar discrete feature distributions closer while pushing the dissimilar further away, in order to better enhance the representation of the latent embedding. Experimental results indicate that GTCoder is effective to generate photo-realistic synthetic data, with interactive interpretation of latent embedding, and performs favorably against some baselines on most real-world and simulated datasets.

Magnetic resonance (MR) image quality assessment plays a crucial role in disease diagnosis and data analysis. Existing methods typically treat the data as images and process them with convolutional networks, thereby ignoring the sequential characteristics of MR data. In this paper, we propose a hybrid spatial-frequency network (HSFNet) for MR image quality assessment, which extracts MR image quality features in both spatial and frequency domains. Specifically, within each data domain, information from local images and global sequences is iteratively integrated by applying a Mamba-based cascading processing module for multiple times. Extensive experiments on both T1-weighting and T2-weighting MR datasets demonstrate the proposed method’s effectiveness and generalization ability in comparison with state-of-the-art MR image quality assessment methods.

No-reference image quality assessment for magnetic resonance images (MRI) aims to generate quality evaluations closely aligned with human perception without the reliance on high-quality reference images. This faces challenges due to the limited availability of large-scale, publicly accessible datasets and the absence of rigorous scientific evaluation. To address these challenges, we underscore the importance of six quality indicators that are closely related to spatial and frequency domain features. Based on these indicators, three experts are employed to provide comprehensive quality ratings across eight public MRI datasets. In addition, we propose a novel approach to extract and combine quality feature representations from spatial and frequency domains. Within the spatial domain, we emphasize capturing anatomical details and structural integrity by applying two sets of data augmentation transformations, which produce data variants that facilitate spatial feature extraction via contrastive learning. Meanwhile, a parallel strategy is carried out in the frequency domain, focusing on signal variations and artifacts. Experimental results demonstrate the robustness of our approach in MRI quality assessment, effectively integrating insights from both spatial and frequency domain perspectives.

Medical image processing plays an important role in the interaction of real world and metaverse for healthcare. Self-supervised denoising based on sparse coding methods, without any prerequisite on large-scale training samples, has been attracting extensive attention for medical image processing. Whereas, existing self-supervised methods suffer from poor performance and low efficiency. In this paper, to achieve state-of-the-art denoising performance on the one hand, we present a self-supervised sparse coding method, named the weighted iterative shrinkage thresholding algorithm (WISTA). It does not rely on noisy-clean ground-truth image pairs to learn from only a single noisy image. On the other hand, to further improve denoising efficiency, we unfold the WISTA to construct a deep neural network (DNN) structured WISTA, named WISTA-Net. Specifically, in WISTA, motivated by the merit of the$l_{p}$-norm, WISTA-Net has better denoising performance than the classical orthogonal matching pursuit (OMP) algorithm and the ISTA. Moreover, leveraging the high-efficiency of DNN structure in parameter updating, WISTA-Net outperforms the compared methods in denoising efficiency. In detail, for a 256 by 256 noisy image, the running time of WISTA-Net is 4.72 s on the CPU, which is much faster than WISTA, OMP, and ISTA by 32.88 s, 13.06 s, and 6.17 s, respectively.

Designing private voting rules is an important and pressing problem for trustworthy democracy. In this paper, under the framework of differential privacy, we propose a novel famliy of randomized voting rules based on the well-known Condorcet method, and focus on three classes of voting rules in this family: Laplacian Condorcet method (CMLAP), exponential Condorcet method (CMEXP), and randomized response Condorcet method (CMRR), where λ represents the level of noise. We prove that all of our rules satisfy absolute monotonicity, lexi-participation, probabilistic Pareto efficiency, approximate probabilistic Condorcet criterion, and approximate SD-strategyproofness. In addition, CMRR satisfies (non-approximate) probabilistic Condorcet criterion, while CMLAP and CMEXP satisfy strong lexi-participation. Finally, we regard differential privacy as a voting axiom, and discuss its relations to other axioms.

The automated generation of radiology reports has attracted significant attention in the field of bioinformatics. Currently, the main limitations of this task include insufficient utilization of prior medical knowledge, lack of efficient knowledge fusion algorithms, and less distinctiveness between different generated reports. To address these issues, we propose a novel algorithm for radiology report generation, which includes Structured Knowledge-Enhanced Multi-modal Attention (SKEMA) and Dual-Branch Contrastive Learning (DBCL) for the first time. SKEMA aims to effectively bridge the gap between visual and prior knowledge by leveraging the high-order adjacency matrix of the knowledge graph to weightedly fuse image features and knowledge features. We enhance both features through masking, and use the original features and augmented features as positive and negative samples in the dual-branch contrastive learning (DBCL). DBCL increases the differences between positive and negative samples to avoid generating templated results, and enhances the robustness of the model. Finally, we conducted experiments to demonstrate the effectiveness of our model on two public radiology datasets, IU-Xray and MIMIC-CXR. Our model outperformed previous baseline methods on both datasets and achieved excellent evaluation scores.

The inadequacy of labeled datasets for image quality assessment has led to the development and popularity of self-supervised approaches. However, most existing self-supervised methods primarily focus on content and fidelity features extracted with convolutional neural networks, overlooking the crucial importance of structural features in quality assessment. To address this problem, we present a novel self-supervised two-stream feature extraction and representation approach. In our approach, the first stream leverages a contrastive learning framework to extract image fidelity features, while the second stream emphasizes structural features by incorporating an attention mechanism. This innovative combination results in a comprehensive feature representation for quality assessment. Moreover, our proposed method facilitates transfer learning, allowing the pre-trained two-stream model in the source domain to be seamlessly applied to target domains for quality regression. This compatibility with transfer learning enhances the adaptability and generalization of the model. Extensive experiments are carried out on three synthetic distortion datasets to validate the effectiveness of our approach. The results demonstrate that our work not only competes with state-of-the-art self-supervised methods but also outperforms some supervised approaches.

For the assignment problem where multiple indivisible items are allocated to a group of agents given their ordinal preferences, we design randomized mechanisms that satisfy first-choice maximality (FCM), i.e., maximizing the number of agents assigned their first choices, together with Pareto efficiency (PE). Our mechanisms also provide guarantees of ex-ante and ex-post fairness. The generalized eager Boston mechanism is ex-ante envy-free, and ex-post envy-free up to one item (EF1). The generalized probabilistic Boston mechanism is also ex-post EF1, and satisfies ex-ante efficiency instead of fairness. We also show that no strategyproof mechanism satisfies ex-post PE, EF1, and FCM simultaneously. In doing so, we expand the frontiers of simultaneously providing efficiency and both ex-ante and ex-post fairness guarantees for the assignment problem.

In the assignment problem, the goal is to assign indivisible items to agents who have ordinal preferences, efficiently and fairly, in a strategyproof manner. In practice, first-choice maximality, i.e., assigning a maximal number of agents their top items, is often identified as an important efficiency criterion and measure of agents' satisfaction. In this paper, we propose a natural and intuitive efficiency property, favoring-eagerness-for-remaining-items (FERI), which requires that each item is allocated to an agent who ranks it highest among remaining items, thereby implying first-choice maximality. Using FERI as a heuristic, we design mechanisms that satisfy ex-post or ex-ante variants of FERI together with combinations of other desirable properties of efficiency (Pareto-efficiency), fairness (strong equal treatment of equals and sd-weak-envy-freeness), and strategyproofness (sd-weak-strategyproofness). We also explore the limits of FERI mechanisms in providing stronger efficiency, fairness, or strategyproofness guarantees through impossibility results.

Approximate nearest neighbour search (ANNS) in high-dimensional space is an essential and fundamental operation in many applications from many domains such as multimedia database, information retrieval and computer vision. With the rapidly growing volume of data and the dramatically increasing demands of users, traditional heuristic-based ANNS solutions have been facing great challenges in terms of both efficiency and accuracy. Inspired by the recent successes of deep learning in many fields, substantial efforts have been devoted to applying deep learning techniques to ANNS for learning to index and learning to search, resulting in numerous algorithms that achieve state-of-the-art performance compared with conventional methods. In this survey paper, we comprehensively review the different types of deep learning-based ANNS methods according to two learning paradigms:learning to indexandlearning to search. We provide a comprehensive overview and analysis of these methods in a systematic manner. Based on the overview, we point out thatend-to-end learningwill be a new and promising research direction for deep learning-based ANNS, i.e., applying deep learning techniques to jointly learn the indexing and searching together, such that the underlying knowledge learned from data can directly contribute to the final searching performance. Finally, we conduct experiments and provide general performance analyses for the representative deep learning-based ANNS algorithms.

Transformer based on self-attention mechanism is blooming in computer vision nowadays. However, its application to video quality assessment (VQA) has not been reported. Evaluating the quality of in-the-wild videos is challenging due to the unknown of pristine reference and shooting distortion. This paper presents a novel space-time attention network for the VQA problem, named StarVQA. StarVQA builds a Transformer by alternately concatenating the divided space-time attention. To adapt the Transformer architecture for training, StarVQA designs a vectorized regression loss by encoding the mean opinion score (MOS) to the probability vector and embedding a special vectorized label token as the learnable variable. To capture the long-range spatiotemporal dependencies of a video sequence, StarVQA encodes the space-time position information of each patch to the input of the Transformer. Various experiments are conducted on the de-facto in-the-wild video datasets, including LIVE-VQC, KoNViD-1k, LSVQ, and LSVQ-1080p. Experimental results demonstrate the superiority of StarVQA over the state-of-the-art. The source code is available at https://github.com/GZHU-DVL/StarVQA.

Learning first-order logic programs (LPs) from relational facts which yields intuitive insights into the data is a challenging topic in neuro-symbolic research. We introduce a novel differentiable inductive logic programming (ILP) model, called differentiable first-order rule learner (DFOL), which finds the correct LPs from relational facts by searching for the interpretable matrix representations of LPs. These interpretable matrices are deemed as trainable tensors in neural networks (NNs). The NNs are devised according to the differentiable semantics of LPs. Specifically, we first adopt a novel propositionalization method that transfers facts to NN-readable vector pairs representing interpretation pairs. We replace the immediate consequence operator with NN constraint functions consisting of algebraic operations and a sigmoid-like activation function. We map the symbolic forward-chained format of LPs into NN constraint functions consisting of operations between subsymbolic vector representations of atoms. By applying gradient descent, the trained well parameters of NNs can be decoded into precise symbolic LPs in forward-chained logic format. We demonstrate that DFOL can perform on several standard ILP datasets, knowledge bases, and probabilistic relation facts and outperform several well-known differentiable ILP models. Experimental results indicate that DFOL is a precise, robust, scalable, and computationally cheap differentiable ILP model.

This paper describes an ultra high definition (UHD) video dataset named DVL2021 for the perceptual study of video quality assessment (VQA). To our knowledge, DVL2021 is the first authentically distorted 4K (3840 × 2160) UHD video quality dataset. The dataset contains 206 versatile 4K UHD video sequences, which are all collected in in-the-wild scenarios. Each sequence is captured at 50 frames per second (fps), stored in raw 10-bit 4:2:0 YUV format, and has a duration of 10 s. Following the subjective evaluation method of TV image quality granted by ITU-R BT.500-13, 32 unique participants take part in the manual annotation process, whose ages are from teenage to sixties (32.7 years old on average). DVL2021 has the following merits: (1) enormous variety of video contents, (2) captured by different types of cameras, (3) complex types and multiple levels of authentic distortion, (4) broadly distributed temporal/spatial information, and (5) a wide spectrum of mean opinion scores (MOS) distribution. Furthermore, we conduct a benchmark experiment by evaluating several mainstream VQA methods on DVL2021. The baseline results are higher than 0.75 in Spearman's rank order correlation coefficient (SROCC) metric. Our study provides a basis for the UHD VQA problem. DVL2021 is publicly available at https://github.com/GZHU-DVL/DVL2021.

We propose multi-type probabilistic serial (MPS) and multi-type random priority (MRP) as extensions of the well-known PS and RP mechanisms to the multi-type resource allocation problems (MTRAs) with partial preferences. In our setting, there are multiple types of divisible items, and a group of agents who have partial order preferences over bundles consisting of one item of each type. We show that for the unrestricted domain of partial order preferences, no mechanism satisfies both sd-efficiency and sd-envy-freeness. Notwithstanding this impossibility result, our main message is positive: When agents' preferences are represented by acyclic CP-nets, MPS satisfies sd-efficiency, sd-envy-freeness, ordinal fairness, and upper invariance, while MRP satisfies ex-post-efficiency, sd-strategyproofness, and upper invariance, recovering the properties of PS and RP. Besides, we propose a hybrid mechanism, multi-type general dictatorship (MGD), combining the ideas of MPS and MRP, which satisfies sd-efficiency, equal treatment of equals and decomposability under the unrestricted domain of partial order preferences.

Physically Unclonable Functions (PUFs), as an alternative hardware-based security method, have been challenged by some modeling attacks. As is known to all, samples are significant in modeling attacks on PUFs, and thus, some efforts have been made to expand sample sets therein to improve modeling attacks. A closer examination, however, reveals that not all samples contribute to modeling attacks equally. Therefore, in this article, we introduce the concept of sample essentiality for describing the contribution of a sample in modeling attacks and point out that any sample without sample essentiality cannot enhance some modeling attacks on PUFs. As a by-product, we find theoretically and empirically that the samples expanded by the procedures proposed by Chatterjee et al. do not satisfy our sample essentiality. Furthermore, we propose the notion of essential sample sets for datasets and discuss its basic properties. Finally, we demonstrate that our results about sample essentiality can be used to reduce samples efficiently and benefit sample selection in modeling attacks on arbiter PUFs.

Holant problem is a general framework to study the computational complexity of counting problems. We prove a complexity dichotomy theorem for Boolean Holant problems with nonnegative algebraic weights. It is the first complete Holant dichotomy where constraint functions are not necessarily symmetric and no auxiliary function is assumed to be available. Let $\mathcal{F}$ be a set of nonnegative functions defined on the Boolean domain. We show that the problem Holant$(\mathcal{F})$ is computable in polynomial time if the function set $\mathcal{F}$ satisfies one of three conditions: (1) every function in $\mathcal{F}$ is a tensor product of functions of arity at most 2; (2) every function in $\mathcal{F}$ is affine; (3) $\mathcal{F}$ is holographically transformable to a product type by some real orthogonal matrix. Otherwise the problem is #P-hard.

Holant problem is a general framework to study the computational complexity of counting problems. We prove a complexity dichotomy theorem for Holant problems over the Boolean domain with non-negative weights. It is the first complete Holant dichotomy where constraint functions are not necessarily symmetric. Holant problems are indeed read-twice #CSPs. Intuitively, some #CSPs that are #P-hard become tractable when restricted to read-twice instances. To capture them, we introduce the Block-rank-one condition. It turns out that the condition leads to a clear separation. If a function set F satisfies the condition, then F is of affine type or product type. Otherwise (a) Holant(F) is #P-hard; or (b) every function in F is a tensor product of functions of arity at most 2; or (c) F is transformable to a product type by some real orthogonal matrix. Holographic transformations play an important role in both the hardness proof and the characterization of tractability.

Modeling and Analysis of Real-Time and Embedded Systems specification (MARTE) is a profile of the Unified Modeling Language (UML) for model driven development of real-time and embedded systems. To describe formally the semantics of MARTE sequence diagram (MARTE SD), we introduce the timing pi-calculus, a new variant of the pi-calculus, in this paper. The good feature of the timing pi-calculus is that it can handle time elapse and timer events. We provide both its syntax and semantics. With the new calculus, we then model MARTE SD elements, and give their precise semantics. Our formal framework may facilitate the reliability and consistency analysis of MARTE SD design process.

The Sequence Diagram (SD) with time properties is frequently used in the preliminary developing phase of embedded reala time system, however, it is not easy to verify due to its informal semantics. An extended time Petri net (TPN) with weak semantics-TLOPNforSD-is defined and proved to be decidable as far as reachability, boundedness and coverability are concerned. A method for progressively refining the SD is also offered in the transformation phase. The SD with time properties are made to be more reliable in two aspects: (1) an enabled transitions generating algorithm based on weak semantics is designed. Based on this algorithm, the verification of SD with time properties in qualitative aspect can be realized by dint of ROMEO; (2) using the state-class diagram obtained in qualitative analysis phase, a scheduling strategy satisfying all the time constraints specified in the SD is worked out. The strategy is used to get compelling time intervals which are more accurate than the static intervals predefined on the SD for every event.

Business Processing Execution Language (BPEL) and BPEL for People (BPEL4People) are two web services orchestration languages for composing web services. To describe formally their semantics, we introduce the πit-calculus, a new variant of the π-calculus, in this paper. The good feature of the πit-calculus is that its execution can be interrupted and can handle timing events as well. We provide both syntax and semantics of the πit-calculus and define a strong bisimulation relation that specifies when two processes can be considered as the same. With the new calculus, we then model the activities of BPEL and BPEL4People, and give their precise semantics. Our formal framework may facilitate the reliability and consistency analysis in a BPEL or BPEL4People design process.

Previous works on formal development for component-based systems usually equate refinement relations as behaviors containment. This setting facilitates verifying safety properties, but can't capture the intuition that a refined component should more easily react to the environment and is not convenient from a point view of design. To address this issue, we argue in favor of defining refinement of component models in terms of alternating simulation, which is a relation on game models with a game-theoretical interpretation. We investigate the refinement relations of component models in the framework of rCOS, which is a formal development method for component systems. We propose the refinement relations of rCOS contract models and specification models respectively and further prove they are alternating simulations. Finally, we define the composition operator on specifications and show the alternating refinement is compositional with respect to this operator.

For some time, the modeling and verification of web services composition are focused on control flow. Recent years, data validation has gained researchers' attention too, as it is important to the correct execution of the composed web service. To verify data-related requirements of web services composition, we present a Petri net-based method for the data validation of web services composition developed with Web Service Business Process Execution Language. Data-flow related aspects of the WS-BPEL process are described with WS-CPN, which is a special kind of Colored Petri net supporting the description of XML Schema types. In WS-CPN, data types are described by CPN ML, a description language for Colored Petri net. We present WS-CPN models for various activities of a WS-BPEL process, which can be combined together to obtain the WS-CPN model for the entire composition process. Data validation problems in web services composition including redundant data, lost data, inconsistent data and misdirected data are discussed, and the methods for validating these problems are given based on WS-CPN.

We define a new temporal logic called CTL[k-QDDC]. It extends CTL with the ability to specify branching pasts and quantitative temporal properties by combining CTL with the logic Quantified Discrete-time Duration Calculus (QDDC). The idea of bounded model checking is also used in this logic. Compared to CTL, the added expressive power is necessary for specification and verification of real-time distributed software and hardware systems. We give the syntax and semantics of CTL[k-QDDC], discuss its expressive power, and propose an explicit model checking algorithm for Kripke structure. CTL[k-QDDC] is considered as a foundation of some more complex logics for specifying and verifying continuous-time properties in some appropriate structures.

Abstract The analysis of workflow is crucial to the correctness of workflow applications. This paper introduces a simple and practical method for analyzing workflow logic models. Firstly, some definitions of the models and some properties, such as throughness, no‐redundant‐transition and boundedness, are presented. Then, we propose an approach based on synchronized reachability graphs (SRGs) to verify these properties. The SRG uses the characteristics of synchronizers in workflow logic models and mitigates the state explosion by constructing synchronized occurrence sequences rather than interleaving occurrence sequences. This paper also proposes some refined and feasible reduction rules which can preserve vital properties of workflow logic models. Using these two techniques, the SRG‐based verification method can achieve higher efficiency. Furthermore, this research also develops a verification tool based on the method, presents the analysis results of some practical cases and compares our method with others. Copyright © 2007 John Wiley & Sons, Ltd.

Abstract There is a growing demand for using commercial‐off‐the‐shelf (COTS) software components to facilitate the development of software systems. Among many research topics for component‐based software, quality‐of‐service (QoS) evaluation is yet to be given the importance it deserves. In this paper, we propose a novel analytical model to evaluate the QoS of component‐based software systems. We use the component execution graph (CEG) graph model to model the architecture at the process level and the interdependence among components. The CEG graph can explicitly capture sequential, parallel, selective and iterative compositions of components. For QoS estimation, each component in the CEG model is associated with execution rate, failure rate and cost per unit time. Three metrics of the QoS are considered and analytically calculated, namely make‐span, reliability and cost. Through a case study, we show that our model is capable of modeling real‐world COTS software systems effectively. Also, Monte‐Carlo simulation in the case study indicates that analytical results are consistent with simulation and all are covered by 95% confidence intervals. We also present a sensitivity analysis technique to identify QoS bottlenecks. This paper concludes with a comparison with related work. Copyright © 2007 John Wiley & Sons, Ltd.

Performance prediction is one of the most important research topics of workflow. To investigate the performance of workflow systems in queuing condition, this paper extends traditional WF-net into WFQN (WF queuing network), by modeling tasks as FIFS (first-in-first-service) queues and the source place as the input of tokens following poisson arrival process. Analytical methods are introduced to evaluate the queue-length, wait-time and completion-duration. The case study (especially the case of airline ticket booking application) shows that WFQN can model real-world workflow-based applications effectively. Through Montecarlo simulations in the case study, we show analytical models are verified by simulative results. We also present a sensitivity analysis technique to identify performance bottle-necks of WFQN. This paper concludes with a comparison with relate work.